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.