Najdłuższy palindrom w stringu

Question

Witam.

Mam takie zadanie: Dla podanego stringa s zwróć najdłuższy palindromiczny string zawarty w s.

Zrobiłem rozwiązanie O(n^3) gdzie n to długość stringa s, nawet zaliczyło mi to rozwiązanie, ale patrząc na statystyki:

Widać że te złożoność da się mocno poprawić. Widziałem jedno rozwiązanie używające programowania dynamicznego, ale też było O(n^2). Więc jak można to inaczej zrobić?

To mój obecny kod:

bool is_palindromic(const std::string& s, const size_t& start, const size_t& end) {
	for (size_t i = start, j = end; i <= j; i++, j--) {
		if (s[i] != s[j])
			return false;
	}

	return true;
}

std::string longestPalindrome(std::string s) {
	std::pair<uint32_t, uint32_t> max = { 0,0 };
	for (uint32_t i = 0; i < s.size(); i++) {
		uint32_t solution = 0;
		for (uint32_t j = i + 1; j < s.size(); j++) {
			if (is_palindromic(s, i, j)) {
				solution = j;
			}
		}

		if (i < solution && solution - i > max.second - max.first)
			max = { i, solution };
	}

	std::string result = "";
	for (uint32_t i = max.first; i <= max.second; i++)
		result += s[i];

	return result;
}

 

Answer 1

Widzę rozwiązanie w O(n log n)

Robisz tablicę haszy prefixów tablicy oraz tablicę haszy prefixów odwróconej tablicy.

Dzięki temu możesz w O(1) sprawdzić czy przedział od a do b jest palindromem po prostu porównując czy pierwszy hasz jest równy drugiemu.

Gdyby wziąć każdy początek i koniec byłoby O(n^2). Można jednak zauważyć, że jak ciąg o danym środku jest palindromem o długości k to będzie także palindromem dla długości k-2 i mniejszych. Można więc wykorzystać binsearcha w następujący sposób:
Przechodzimy po każdym elemencie w tablicy i zakładamy że jest środkiem palindromu i próbujemy binsearchem zgadnąć jak długim jest palindromem (zajmie do czas O(log n) dla pojedynczego elementu). Analogicznie można zrobić dla panlidromów z parzystymi długościami. Złożoność (n log n)

Comments

Co znaczy "tablica haszy prefixów"? Mam brać hash dla każdego możliwego podstringa i dla jego odwrotności? Na pewno nie rozumiem, bo to już by było O(n^2). I też nie rozumiem o co chodzi z tym, że jeśli "ciąg o danym środku jest palindromem o długości k to będzie także palindromem dla dlugości k-2 i mniejszych", np. weźmy wyraz "kajak", odejmę np. 2, będzie "kaj" i to przecież nie jest palindrom. Właściwie to chyba nic nie zrozumiałem :/

---

dla każdego elementu w tablicy uruchamiaj pętlę sprawdzającą elementy +1 -1, aż 1) nie dojdzie do końca tablicy, 2) dokąd element -1 +1 są takie same. jak pętla się uruchomi chociaż raz dodawaj do tablicy pomocniczej aktualny rozmiar

---

Na pewno nie rozumiem, bo to już by było O(n^2).

Nikt nie powiedział że musisz dla każdego zakresu wołać substring() i liczyć od zera hash tego substringa. Wystarczy że podczas iteracji będziesz na bieżąco budował hash dodając jedynie kolejne znaki.

---

Chodzi o haszowanie jak w algorytmie Karpa-Rabina: https://eduinf.waw.pl/inf/alg/001_search/0052.php

Chcąc sprawdzić w czasie O(1) czy tekst od i do i+k jest palidromem zrobiłbyś coś w tym rodzaju: (może nie zgadzać się wyliczenie indeksu, sprawdź to sobie)

long long h1 = hash[i+k] - hash[i-1];
long long h2 = hash[n-(i+1)] - hash[n-(i+k+2)];
if(h1 == h2)
   cout << "ciąg jest palindromem";

Jak weźmiemy środek palidroma kajak i odejmiemy tyle samo znaków z lewej co z prawej to dalej jest to palindrom - o to chodziło.