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 ;)

2

Ilustracja mojego wygląda tak:

#include <iostream>

using namespace std;

bool palindromeFound(const string &s)
{
    if (s.size() == 2)
    {
        return s[0] == s[1];
    }
    if (s.size() >= 3)
    {
        int index = 1;
        do
        {
            if (s[index - 1] == s[index + 1] || s[index] == s[index - 1])
            {
                return true;
            }
            index++;
        }
        while (index < s.size());
    }
    
    return false;
}

int main()
{
    string stringWithPalindrome = "abbaddon";
    //string stringWithPalindrome = "abcbaz";
    //string stringWithPalindrome = "dupaa";
    //string stringWithPalindrome = "kajak";
    
    if (palindromeFound(stringWithPalindrome))
    {
        cout << "palindrome found in string: " << stringWithPalindrome;
    }
    else
    {
        cout << "the string: " << stringWithPalindrome <<" does not contain a palindrome";
    }
    
    return 0;
}
0

@MarekR22: especially for you

bool palindromeFound(const string &s){
  for(int i=0; i < (signed) s.size()-1; i++){
    if (s[i] == s[i + 1] || s[i] == s[i < s.size() - 2 ?  i + 2 : i + 1])
      return true;
  }
  return false;
}

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