Nejdelší palindromický podřetězec v řetězci v Javě
Table of Contents
Úvod
Palindrom je posloupnost znaků, která se čte stejně zleva doprava i zprava doleva. Například slovo „kayak“ je palindrom, protože se čte stejně oběma směry. V mnoha aplikacích může být užitečné najít nejdelší palindromický podřetězec v daném řetězci. Například se to používá v bioinformatice pro porovnávání sekvencí DNA.
V tomto článku probereme dva různé algoritmy pro nalezení nejdelšího palindromického podřetězce v řetězci Java: Algoritmus dynamické programování* a *Algoritmus Manacher.
Algoritmus dynamické programování
Algoritmus dynamické programování pro hledání nejdelšího palindromického podřetězce v řetězci je založen na principu optimality, který říká, že optimální řešení podproblému je součástí optimálního řešení původního problému.
Kroky algoritmu:
1. Vytvořte dvourozměrnou tabulku dp, kde dp[i][j] představuje nejdelší palindromický podřetězec v řetězci od i-tého znaku po j-tý znak.
2. Inicializujte dp[i][i] na 1 pro všechny i (jednopísmenné palindromy).
3. Pro výpočet dp[i][j] pro i < j postupujte podle následujících kroků:
– Pokud je s[i] == s[j], nastavte dp[i][j] na dp[i+1][j-1] + 2.
– Jinak nastavte dp[i][j] na maximum hodnot dp[i][j-1], dp[i+1][j] a dp[i+1][j-1].
4. Nejdelší palindromický podřetězec je určen hodnotou dp[0][s.length() - 1].
Příklad implementace v Javě:
java
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();
}
}
Algoritmus Manacher
Algoritmus Manacher je efektivnější algoritmus pro nalezení nejdelšího palindromického podřetězce v řetězci. Používá techniku předzpracování pro vytvoření rozšířeného řetězce, který obsahuje speciální znaky mezi znaky původního řetězce.
Kroky algoritmu:
1. Předzpracujte řetězec vložením speciálních znaků # mezi znaky.
2. Pro každý znak c rozšířeného řetězce vytvořte střed i a poloměr r palindromu.
3. Rozšiřujte poloměr palindromu, dokud nesplní podmínku i - r >= 0 a i + r < n a znaky na pozicích i - r a i + r se rovnají.
4. Aktualizujte poloměr palindromu, pokud je větší než aktuální největší poloměr.
5. Vraťte nejdelší palindromický podřetězec, jehož střed je v původním řetězci.
Příklad implementace v Javě:
java
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
V tomto článku jsme probrali dva účinné algoritmy pro nalezení nejdelšího palindromického podřetězce v řetězci v Javě: Algoritmus dynamické programování a Algoritmus Manacher. Oba algoritmy jsou efektivní, ale algoritmus Manacher je obvykle rychlejší. Volba algoritmu závisí na konkrétních požadavcích aplikace.