Cel mai lung subșir palindrom într-un șir în Java

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 cu j, atunci dp[i][j] este setat la 1, deoarece un singur caracter este, prin definiție, un palindrom.
  • Dacă i + 1 este egal cu j, atunci dp[i][j] devine 2 dacă simbolurile de la pozițiile i și j sunt identice; în caz contrar, dp[i][j] va fi 1.
  • Dacă i + 1 este mai mic decât j, atunci dp[i][j] este egal cu 2 plus lungimea celui mai extins subșir palindrom localizat în secțiunea care începe de la indexul i + 1 și se termină la indexul j - 1, cu condiția ca simbolurile de la pozițiile i și j să fie identice; altfel, dp[i][j] va fi maximul dintre valorile dp[i + 1][j] și dp[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ât r[c], atunci p[i] primește valoarea minimă dintre r[c] - i și p[2 * c - i], unde c 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ă în p[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.