Introducere
A identifica cel mai extins subșir palindrom într-un șir de caractere reprezintă o provocare fundamentală în programare, punând la încercare abilitățile de algoritmizare și de manipulare a șirurilor. Un subșir palindrom este definit ca o porțiune dintr-un șir inițial, care păstrează aceeași formă, indiferent de direcția de citire, de la stânga la dreapta sau invers. Spre exemplu, în șirul „radar”, întregul șir „radar” este, de asemenea, cel mai lung subșir palindrom.
Există diverse modalități de abordare a acestei probleme, însă cele mai des întâlnite sunt:
- Metoda programării dinamice: Aceasta presupune construirea unei structuri de date tip matrice, unde sunt înregistrate informații despre subșirurile palindromice descoperite. Ulterior, aceste date sunt folosite pentru a determina cel mai lung subșir palindrom.
- Algoritmul lui Manacher: Acest algoritm scanează șirul o singură dată, creând o matrice în care sunt stocate lungimile celor mai extinse subșiruri palindromice, centrate în jurul fiecărui caracter din șirul original.
Algoritmul bazat pe programare dinamică
Metoda programării dinamice operează prin generarea unei matrici dp
, unde dp[i][j]
indică cel mai lung subșir palindrom din șirul inițial, care începe de la indexul i
și se termină la indexul j
. Matricea dp
este populată gradual, pornind de la subșirurile cele mai scurte și ajungând la cele mai lungi. Pentru a calcula valoarea dp[i][j]
, algoritmul analizează următoarele situații:
- Dacă
i
este identic cuj
, atuncidp[i][j]
este setat la 1, deoarece un singur caracter este, prin definiție, un palindrom. - Dacă
i + 1
este egal cuj
, atuncidp[i][j]
devine 2 dacă simbolurile de la pozițiilei
șij
sunt identice; în caz contrar,dp[i][j]
va fi 1. - Dacă
i + 1
este mai mic decâtj
, atuncidp[i][j]
este egal cu 2 plus lungimea celui mai extins subșir palindrom localizat în secțiunea care începe de la indexuli + 1
și se termină la indexulj - 1
, cu condiția ca simbolurile de la pozițiilei
șij
să fie identice; altfel,dp[i][j]
va fi maximul dintre valoriledp[i + 1][j]
șidp[i][j - 1]
.
Algoritmul Manacher
Algoritmul lui Manacher procesează șirul printr-o singură trecere, construind o matrice p
, unde p[i]
reprezintă lungimea celui mai mare subșir palindrom centrat în jurul caracterului de la indexul i
. Acest algoritm folosește o matrice auxiliară r
pentru a stoca marginile celui mai lung subșir palindrom cunoscut până la momentul actual.
Calculul valorii p[i]
se face analizând următoarele scenarii:
- Dacă
i
este mai mic decâtr[c]
, atuncip[i]
primește valoarea minimă dintrer[c] - i
șip[2 * c - i]
, undec
reprezintă centrul celui mai extins subșir palindrom cunoscut până în acel moment. - În situația contrară, algoritmul extinde palindromul având centrul în caracterul de la poziția
i
, atât către stânga cât și către dreapta, până când este întâlnit un caracter care nu mai face parte din palindrom. Lungimea palindromului rezultat este apoi salvată înp[i]
.
Implementare Java
Următoarele fragmente de cod Java prezintă implementările algoritmilor de programare dinamică și a celui lui Manacher, pentru a identifica cel mai lung subșir palindrom într-un șir:
Algoritmul de programare dinamică:
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:
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
Identificarea celui mai extins subșir palindrom într-o secvență de caractere este o problemă clasică în informatică, ce poate fi soluționată prin diferite metode. Algoritmii de programare dinamică și cel al lui Manacher reprezintă două dintre cele mai performante abordări, implementabile în diverse limbaje de programare, inclusiv Java. Alegerea algoritmului optim pentru o anumită situație 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 identic de la stânga la dreapta și invers.
- Un subșir palindrom este o porțiune dintr-un șir, care respectă proprietatea de a fi palindrom.
2. Care este complexitatea temporală și spațială a algoritmului de programare dinamică pentru identificarea 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 temporală a algoritmului lui Manacher pentru identificarea celui mai lung subșir palindrom?
Complexitatea temporală este O(n), unde n este lungimea șirului.