Nejdelší palindromický podřetězec v řetězci v Javě

Palindrom je sekvence znaků, která zůstává stejná, ať už je čtena zleva doprava, nebo zprava doleva. Slovo jako "rotor" je typickým příkladem palindromu. V mnoha situacích je potřeba v daném řetězci vyhledat ten nejdelší palindromický podřetězec. Taková operace má uplatnění třeba v bioinformatice při analýze a porovnávání sekvencí DNA.

Tento článek se zaměří na dva odlišné přístupy k řešení tohoto problému v jazyce Java: Metodu dynamického programování a Manacherův algoritmus.

Dynamické programování

Metoda dynamického programování pro hledání nejdelšího palindromického podřetězce se opírá o princip optimality, který zjednodušeně říká, že optimální řešení menších dílčích problémů je součástí optimálního řešení celého problému.

Kroky algoritmu:

1. Vytvoříme dvourozměrnou tabulku dp. Prvek dp[i][j] bude uchovávat délku nejdelšího palindromického podřetězce v daném řetězci v rozsahu znaků od indexu i do indexu j.
2. Iniciačně nastavíme všechny hodnoty dp[i][i] na 1, protože každý jednotlivý znak je sám o sobě palindromem.
3. Pro výpočet hodnot dp[i][j], kde i je menší než j, provedeme následující:
   • Pokud se znaky na pozicích s[i] a s[j] shodují, dp[i][j] nastavíme na hodnotu dp[i+1][j-1] + 2.
   • Pokud se znaky neshodují, dp[i][j] nastavíme na maximum z hodnot dp[i][j-1], dp[i+1][j] a dp[i+1][j-1].
4. Délka nejdelšího palindromického podřetězce se nakonec uloží v dp[0][s.length() - 1].

Příklad implementace v Javě:

public class PalindromickyPodretezec { public static void main(String[] args) { String s = "kayak"; System.out.println(nejdelsiPalindromickyPodretezec(s)); // Výstup: kayak } public static String nejdelsiPalindromickyPodretezec(String s) { int n = s.length(); int[][] dp = new int[n][n]; // Jednopísmenné palindromy for (int i = 0; i < n; i++) { dp[i][i] = 1; } // Palindromy délky 2 for (int i = 0; i < n - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { dp[i][i + 1] = 2; } } // Palindromy délky větší než 2 for (int l = 3; l <= n; l++) { for (int i = 0; i <= n - l; i++) { int j = i + l - 1; if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] > 0) { dp[i][j] = l; } else { dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]); } } } // Získání nejdelšího palindromického podřetězce StringBuilder sb = new StringBuilder(); int start = 0; int end = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dp[i][j] > end - start) { start = i; end = j; } } } for (int i = start; i <= end; i++) { sb.append(s.charAt(i)); } return sb.toString(); } }

Manacherův algoritmus

Manacherův algoritmus je považován za efektivnější metodu pro hledání nejdelšího palindromického podřetězce. Jeho klíčem je předzpracování řetězce, které spočívá v přidání speciálních znaků mezi jednotlivé znaky původního řetězce.

Kroky algoritmu:

1. Upravíme původní řetězec tak, že mezi všechny znaky a na jeho začátek a konec vložíme znak '#'.
2. Pro každý znak c v upraveném řetězci určíme střed i a poloměr r palindromu.
3. Poloměr palindromu rozšiřujeme tak dlouho, dokud platí podmínka, že i - r je větší nebo rovno 0, i + r je menší než délka řetězce a současně se znaky na pozicích i - r a i + r shodují.
4. Aktualizujeme poloměr palindromu, pokud je delší než aktuálně nejdelší nalezený poloměr.
5. Vracíme nejdelší palindromický podřetězec, který má střed v původním řetězci.

Příklad implementace v Javě:

public class PalindromickyPodretezecManacher { public static void main(String[] args) { String s = "kayak"; System.out.println(nejdelsiPalindromickyPodretezecManacher(s)); // Výstup: kayak } public static String nejdelsiPalindromickyPodretezecManacher(String s) { // Předzpracování StringBuilder sb = new StringBuilder(); sb.append('#'); for (char c : s.toCharArray()) { sb.append(c); sb.append('#'); } String t = sb.toString(); // Vytvoření pole P s poloměry palindromů int n = t.length(); int[] p = new int[n]; int center = 0; int right = 0; int maxLen = 0; int maxCenter = 0; for (int i = 1; i < n; i++) { int mirror = 2 * center - i; if (i < right) { p[i] = Math.min(right - i, p[mirror]); } // Rozšiřování palindromu while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) { p[i]++; } // Aktualizace maxima if (p[i] > maxLen) { maxLen = p[i]; maxCenter = i; } // Aktualizace středu a krajního bodu if (i + p[i] > right) { center = i; right = i + p[i]; } } // Získání nejdelšího palindromického podřetězce StringBuilder result = new StringBuilder(); for (int i = maxCenter - maxLen; i <= maxCenter + maxLen; i++) { if (t.charAt(i) != '#') { result.append(t.charAt(i)); } } return result.toString(); } }

Závěr

Tento článek představil dva algoritmy pro vyhledávání nejdelšího palindromického podřetězce v řetězci v jazyce Java: Dynamické programování a Manacherův algoritmus. Obě metody jsou účinné, ale Manacherův algoritmus bývá zpravidla rychlejší. Volba vhodného algoritmu závisí na specifických požadavcích daného úkolu.