Cuprins
Cel mai lung subșir palindrom într-un șir în Java
Introducere
Identificarea celui mai lung subșir palindrom într-un șir este o problemă clasică de programare care testează abilitățile de algoritmică și de manipulare a șirurilor. Un subșir palindrom este o secvență de caractere dintr-un șir original care se citește la fel de la stânga la dreapta și de la dreapta la stânga. De exemplu, în șirul „racecar”, cel mai lung subșir palindrom este „racecar” însuși.
Există mai multe abordări pentru a rezolva această problemă, dar două dintre cele mai comune includ:
* Algoritmul de programare dinamică: Această abordare construiește o matrice care memorează informații despre subșirurile palindrome găsite până în momentul respectiv. Folosește apoi aceste informații pentru a calcula cel mai lung subșir palindrom.
* Algoritmul Manacher: Acest algoritm procesează șirul într-o singură trecere, creând o matrice care memorează lungimile celor mai lungi subșiruri palindrome centrate pe fiecare caracter din șirul original.
Algoritmul de programare dinamică
Algoritmul de programare dinamică funcționează prin construirea unei matrice dp în care dp[i][j] reprezintă cel mai lung subșir palindrom din șirul original care începe la indexul i și se termină la indexul j. Algoritmul umple matricea dp pornind de la cele mai mici subșiruri și mergând până la cele mai mari. Pentru a calcula dp[i][j], algoritmul verifică următoarele cazuri:
* Dacă i este egal cu j, atunci dp[i][j] este egal cu 1, deoarece un singur caracter este întotdeauna un palindrom.
* Dacă i + 1 este egal cu j, atunci dp[i][j] este egal cu 2 dacă caracterele de la indexul i și j sunt egale; în caz contrar, dp[i][j] este egal cu 1.
* Dacă i + 1 este mai mic decât j, atunci dp[i][j] este egal cu 2 plus lungimea celui mai lung subșir palindrom din șirul care începe la indexul i + 1 și se termină la indexul j - 1, dacă caracterele de la indexul i și j sunt egale; în caz contrar, dp[i][j] este egal cu maximum dintre dp[i + 1][j] și dp[i][j - 1].
Algoritmul Manacher
Algoritmul Manacher procesează șirul într-o singură trecere, creând o matrice p în care p[i] reprezintă lungimea celui mai lung subșir palindrom centrat pe caracterul de la indexul i. Algoritmul folosește un array r pentru a memora limitele celui mai lung subșir palindrom cunoscut până în prezent.
Pentru a calcula p[i], algoritmul verifică următoarele cazuri:
Dacă i este mai mic decât r[c], atunci p[i] este egal cu minimum dintre r[c] - i și p[2 c - i], unde c este centrul celui mai lung subșir palindrom cunoscut până în prezent.
* În caz contrar, algoritmul extinde palindromul centrat pe caracterul de la indexul i spre stânga și spre dreapta, până când găsește un caracter care nu aparține palindromului. Lungimea palindromului extins este apoi stocată în p[i].
Implementare în Java
Următoarele coduri Java implementează algoritmii de programare dinamică și Manacher pentru a găsi cel mai lung subșir palindrom într-un șir:
Algoritmul de programare dinamică:
java
public class LongestPalindromicSubstring {
public static String longestPalindromicSubstring(String str) {
int n = str.length();
int[][] dp = new int[n][n];
int maxLength = 1;
int start = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
if (i < n - 1 && str.charAt(i) == str.charAt(i + 1)) {
dp[i][i + 1] = 2;
maxLength = 2;
start = i;
}
}
for (int k = 3; k <= n; k++) {
for (int i = 0; i < n - k + 1; i++) {
int j = i + k - 1;
if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1] > 0) {
dp[i][j] = dp[i + 1][j - 1] + 2;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
start = i;
}
}
}
}
return str.substring(start, start + maxLength);
}
public static void main(String[] args) {
String str = "racecar";
String longestPalindromicSubstring = longestPalindromicSubstring(str);
System.out.println("Cel mai lung subșir palindrom este: " + longestPalindromicSubstring);
}
}
Algoritmul Manacher:
java
public class LongestPalindromicSubstring {
public static String longestPalindromicSubstring(String str) {
int n = str.length();
int[] p = new int[n];
int c = 0;
int r = 0;
int maxLength = 0;
int start = 0;
for (int i = 0; i < n; i++) {
int mirror = 2 * c - i;
if (i < r) {
p[i] = Math.min(r - i, p[mirror]);
}
while (i - p[i] >= 0 && i + p[i] < n && str.charAt(i - p[i]) == str.charAt(i + p[i])) {
p[i]++;
}
if (i + p[i] > r) {
c = i;
r = i + p[i];
}
if (p[i] > maxLength) {
maxLength = p[i];
start = i - maxLength + 1;
}
}
return str.substring(start, start + maxLength);
}
public static void main(String[] args) {
String str = "racecar";
String longestPalindromicSubstring = longestPalindromicSubstring(str);
System.out.println("Cel mai lung subșir palindrom este: " + longestPalindromicSubstring);
}
}
Concluzie
Găsirea celui mai lung subșir palindrom într-un șir este o problemă clasică de programare care poate fi rezolvată folosind diverse abordări. Algoritmii de programare dinamică și Manacher sunt două dintre cele mai eficiente abordări și pot fi implementate în mai multe limbaje de programare, inclusiv Java. Alegerea celui mai potrivit algoritm pentru o anumită problemă depinde de factori precum lungimea șirului, complexitatea algoritmului și cerințele de performanță.
Întrebări frecvente
1. Care este diferența dintre un palindrom și un subșir palindrom?
* Un palindrom este un șir care se citește la fel de la stânga la dreapta și de la dreapta la stânga.
* Un subșir palindrom este o secvență de caractere dintr-un șir original care se citește la fel de la stânga la dreapta și de la dreapta la stânga.
2. Care este complexitatea algoritmului de programare dinamică pentru găsirea celui mai lung subșir palindrom?
* Complexitatea temporală este O(n^2), unde n este lungimea șirului.
* Complexitatea spațială este O(n^2).
3. Care este complexitatea algoritmului Manacher pentru găsirea celui mai lung subșir palindrom?
* Complexitatea temporală este O(n), unde n