Wyszukiwanie palindromu wewnątrz zadanego ciągu znaków

0

Witam,

mam problem z takim zadaniem:
http://solve.edu.pl/contests/download_desc/1873

Nie wiem jak sobie poradzić z występowaniem palindromu w ciągu znaków.
Napisałem kod na to czy wyraz jest lub nie jest palindromem (0 - nie jest, 1 - jest) ale czy w danym ciągu jest palindrom przechodzi moje umiejętności.

#include <iostream>

using namespace std;

bool czy_pal(const string ciag_znakow)
{
    bool jest=true;
    for(int i=0, j=ciag_znakow.length()-1; i<j; i++, j--)
    if(ciag_znakow[i]!=ciag_znakow[j])
    {
        jest=false; 
        break;
    }

    return (jest==true) ?  true :  false;
}

int main()
{
    string ciag_znakow;
    cin >> ciag_znakow;
    cout << czy_pal(ciag_znakow);

    return 0;
}
0

Zależy jakie dane masz na wejściu, jeśli są to normalne zdania, np:
"Ładny kajak cieszy oko"
to wpierw podziel ciąg znaków na pojedyncze słowa po spacji, po czym używaj swojej funkcji do wykrywania palindromów aby sprawdzić każde słowo z osobna. Jak nie wykryje ani jednego palindromu to masz odpowiedź.

1

Na wejściu jest ciąg znaków:

Wejście: Wejście:
abcdajk abcbaz
Wyjście: Wyjście:
NIE TAK
0

ten kod źle wczytuje dane. Jeśli nie umiesz zrozumieć treści opisującej dane wejściowe, to wątpię żebyś poradził sobie z samym zadaniem.

0

Mam kod z ilością wykonanych testów i trochę inny:


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
using namespace std;

int main()
{
   int t;
   cin >> t;
   while(t--)
   {

string wyraz; int ostatnia;
cin>>wyraz;
ostatnia=wyraz.size()-1;
for(int i=0; i<=ostatnia; i++)
{
    if(wyraz[i]!=wyraz[ostatnia-i])
        {
        cout<<"NIE";
        break;
       }
       else if(i==ostatnia)
        cout<<"TAK";

}
getchar();

   }
   return 0;
}
3

Skoro to jeden ciąg znaków, to inaczej się trzeba wziąć do sprawy.
Zwróć uwagę Bracie, że każdy ciąg o długości 2 będzie palindromem jeśli oba znaki są te same. Natomiast w ciągach dłuższych minimalna próbka pozwalająca zweryfikować palindrom to 3. Zatem algorytm wyglądałby jakoś tak:
1) ciąg.długość == 2 ? => sprawdzasz czy oba znaki są takie same. Jak są to palindrom. Dzięki Bracie @Delor za sprostowanie.
2) ciąg.długość >= 3? ustaw wskaźnik na element o indeksie index = 1
3) sprawdź czy znak będący na index - 1 == index + 1.
3a) Odpowiedź pozytywna => jest palindrom
3b) Odpowiedź negatywna => index++, sprawdź, czy index + 1 < ciąg.size, jeśt tak to powtóż krok 3, jeśli nie => zakończ szukanie z odpowiedzią "nie ma palindromu"
Przykłady:
oko => wiadomo
kajak => wskaźnik na a, i na pozycji o 1 w lewo jest k, a na pozycji o 1 w prawo j. Nie ma palindromu, to wskaźnik na j, i powtórka -> teraz z obu stron jest a, więc palindrom
abcbaz => wskaźnik na b, na lewo o 1 a, na prawo o 1 c. Nope, przestawiamy wskaźnik o 1 w prawo, i teraz palindrom bcb zostanie wykryty.

Algortym można rozwinąć, aby po wykryciu 3-elementowego zalążka palindromu sprawdzał, jak daleko się on rozciąga, a także aby wyszukiwał ile palindromów w podanym ciągu znalazł.

EDIT:
Aaaa,jeszcze trzeba rozważyć taki przypadek:
abbadon
powinien zostać wykryty jako palindrom, a powyższy algorytm na nim polegnie. Poprawka do kroku 3 to dodać kolejny warunek:
[index - 1] == [index]

0

Jakoś tak (mogą być błędy):

bool is_palindrome(const char *p1, const char *p2)
{
    while(p1 < p2 && *p1 == *p2) { ++p1; --p2; }
    return p1 >= p2;
}

bool check_word(const char* str, size_t len) 
{
    const char *p1 = str;
    const char *p2 = str + len - 1;

    while(p1 < p2)
    {
        const char* p3 = p2;
        while(p3 > p1 && *p3 != *p1) --p3;
        if(p3 - p1 > 1 && is_palindrome(p1, p3)) return true;
        ++p1;
    }

    return false;
}
char str[100] = "abcbaz";
size_t len = strlen(str);

std::cout << (check_word(str, len) ? "TAK\n" : "NIE\n");
1

Tak będzie działać:

bool has_palindrome(string a) {
    const int limit = a.length();
    if (limit < 2) return false;

    else if (limit == 2) {
        return (a[0] == a[1]);
    }

    else {
        for (int i = 1; i < limit - 1; i++ ) {
            if ( (a[i - 1] == a[i] || a[i + 1] == a[i]) || a[i - 1] == a[i + 1]) return true;
        }
    }
    return false;
}

EDIT: Już nieistotne: Pozostaje kwestia pustego stringa, z treści wynika, imo, że się nie pojawi na wejściu.
EDIT 2: Był bug, dodany warunek wyłapujący cały również cały palindrom.

1
bool containsPalindorme(std::string_view a)
{
   if (a.size() < 2) return false;

   for (size_t subLen= 2; subLen <= a.size(); ++subLen) {
       for (size_t i = 0; i + subLen <= a.size(); ++i) {
            if (std::search(a.begin(), a.end(), a.rbegin() + 1, a.rbegin() +  i + subLen)  != a.end()) {
                return true;
            }
       }
   }
   return false;
}

To jest do d**y, naiwne bo złożoność wychodzi O(n^3) O(n^4) (dwa for dają O(n^2), a serach ma złożoność O(n^2) a nie liniową).
MasterBLB daje proste i szybkie rozwiązanie.

2

Przecież nie szukasz całego palindromu, tylko czy jest palindrom, czyli najkrótszy możliwy np. aa lub aba, Wystarczy, że sprawdzisz, czy gdzieś w łańcuchy spełniona jest jedna z równości:
a[i] == a[i+1], o długości parzystej
a[i-1] == a[i+1] , o długości nieparzystej
Robisz pętle i jedziesz ;)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0