Problem najdužeg palindroma u stringu

U informatici, problem najdužeg palindroma u stringu ili najveći simetrični faktor je problem nalaženja najdužeg podstringa datog stringa, podstring mora biti palindrom. Na primer, najduži palindrom u reči "banana" je "anana". Najduži palindrom ne mora biti jedinstven; na primer, u stringu "abrakadabra", ne postoji palindrom koji ima više od tri slova, ali postoje dva palindroma sa dužinom tri, konkretno, "aka" i "ada". U nekim primenama je potrebno vratiti sve najveće palindrome (odnosno, sve podstringove koji su palindromi i ne mogu biti prošireni a da pritom zadrže svojstvo palindroma) umesto vraćanja samo jednog od najdužih palindroma ili dužine najvećeg palindroma u okviru stringa..

Glen Manaker 1975 je našao algoritam u linearnom vremenu za listanje svih palindroma koji se pojavljuju na početku stringa. Međutim, Apostolico, Breslauer & Galil 1995, su primetili da se isti algoritam može upotrebiti za nalaženje najvećih palindroma u stringu, nebitno od pozicije palindroma, opet u linearnom vremenu. Dakle, pruža rešenje na problem nalaženja najdužeg palindroma u stringu u linearnom vremenu. Alternativno rešenje koje se takođe izvršava u linearnom vremenu su pružili Jeuring 1994 i Gusfield 1997, koji su opisali rešenje zasnovano na sufiksnom stablu. Poznat je i efikasni paralelni algoritam za ovaj problem.

Najduži palindrom u stringu ne sme biti pomešan sa drugim problemom nalaženja najdužeg podskupa koji zadovoljava svojstvo palindroma. Podskup stringa iako zadovoljava svojstvo, u opisu problema, da se karakteri pojavljuju u rastućem redosledu (u smislu prvi član podskupa se sigurno pojavljuje pre drugog i tako redom) ne podrazumeva se da su članovi podskupa UZASTOPNI, što je uslov kod najdužeg palindroma u stringu.

Manakerov algoritam

Da bi našli u linearnom vremenu najduži palindrom u stringu, algoritam koristi određene karakteristike i zaključke o palindromima i pod-palindormima (u ovom kontekstu palindrom sa tendencijom rasta, na primer reč "ada" može se proširiti u "radar"):

1. Leva strana palindroma je desne strana "u ogledalu" (odnosno kada bi počeli sa početka leve i kraja desne strane i iterirali ka unutra slova kroz koja bi prolazili bi bila ista).
2. Termin u ogledalu ćemo koristiti da obeležimo karakter koji se nalazi na poziciji koja udaljena od desnog kraja isto onoliko koliko je pozicija trenutnog karaktera udaljena od levog kraja, pod uslovom da je karakter bliži desnom kraju palindroma, u suprotnom je situacija obrnuta.
3. (Slučaj 1) Ako treći palindrom čiji je centar u okviru desne strane prvog palindroma će imati tačno istu dužinu kao i drugi palindrom koji počinje sa mesta koje je "u ogledalu" u odnosu na početak trećeg palindroma ako je drugi palindrom u okviru granica prvog palindroma, sa odstupanjem za najmanje jedan karakter.
4. (Slučaj 2) Ako drugi palindrom dodiruje ili se prostire van leve granice prvog palindroma onda je treći palindrom garantavano najmanju dužinu koja iznosi dužinu od sopstvenog centra do najviše desnog karaktera prvog palindroma. Ova dužina je ista kao i dužina od centra drugog palindroma do najviše levog karaktera prvog palindroma.
5. Da bi našli dužinu trećeg palindroma iz slučaja 2, sledeći karakter posle najviše desnog karaktera prvog palindroma bi trebalo da bude poređen sa njegovim "odrazom u ogledalu" od centra trećeg palindrom, dok se ne poklope karakteri ili nema više karaktera za poređenje.
6. (Slučaj 3) Ni prvi ni drugi palindrom ne pružaju informacija koje bi pomogle da se odredi dužina četvrtog palindroma čiji je centar izvan desne strane prvog palindroma.
7. Dakle poželjno bi bilo da imamo palindrom kao referencu (odnosno ulogu prvog palindroma) koji poseduje karaktere najdalje desno u stringu, kada nalazimo sleva ka desno dužinu palindroma u stringu (i stoga treći palindrom u drugom slučaju i četvrti palindrom u trećem slučaju mogu zameniti prvi palindrom kao novu referencu).
8. Što se tiče vremenske složenosti nalaženja dužine palindroma za svaki karakter u stringu, ne postoji poređenje karaktera za prvi slučaj, dok za drugi i treći samo karakteri u stringu koji se nalaze izvan najviše desnog karatera referentnog palindroma su kandidati za poređenje (i stoga treći slučaj će uvek rezultovati novim referentnim (prvim) palindromom dok drugi slučaj rezultuje novim referentnim palindromom samo ako je treći palindrom zapravo duži od garantovane minimalne dužine).
9. Za palindrom parne dužine, centar je na granici dva srednja karaktera

Implementacija

Neka je:

• s je string od N karaktera
• s2 izveden string od s, koji obuhvata N * 2 + 1 elemenata, gde svaki element odgovara jednom od sledećih slučajeva: N karatera u s, N-1 granica između karaktera, i granice pre i posle prvog i poslednjeg karatera respektivno.
• Granica u s2 je jednaka bilo kojoj drugoj granici u s2 u pogledu usklađenosti elemenata u određivanju dužine palindroma.
• p niz palindromskih razmaka za svaki element u s2, od centra do bilo kog graničnog elementa, gde se svaka granica uračunava u palindrom (to jest palindrom koji ima samo tri elementa ima palindromsku dužinu 1)
• c je pozicija centra palindroma za koji trenutno znamo da uključuje granicu najbližu desnom kraju stringa s2 (to jest, dužina palindroma = p[c]*2+1)
• r je pozicija najviše desne granice ovog palindroma (to jest, r = c + p[c])
• i je pozicija elementa (to jest, karakter ili granica) u s2 čija se palindromska dužina određuje, pritom je i uvek desno od c
• i2 je pozicija u ogledalu od i oko c (to jest, {i, i2} = {6, 4}, {7, 3}, {8, 2},… kada je c = 5 (to jest, i2 = c * 2 - i)

C++ implementacija

#include <string>
#include <vector>
#include <iostream>

std::vector<char> addBoundaries(std::vector<char> cs) {
  if(cs.size() == 0){
    std::vector<char> cs2;
    cs2.push_back('|');
    cs2.push_back('|');
    return cs2;
  }
  std::vector<char> cs2(cs.size()* 2 + 1);
  for(int i = 0; i < (cs2.size() - 1); i += 2) {
    cs2[i] = '|';
    cs2[i+1] = cs[i/2];
  }
  cs2[cs2.size()-1] = '|';
  return cs2;
}
 
std::vector<char> removeBoundaries(std::vector<char> cs) {
  if(cs.size() < 3) {
    std::vector<char> cs2;
    return cs2;
  }
  std::vector<char> cs2((cs.size()-1)/2);
  for (int i = 0; i < cs2.size(); ++i) {
    cs2[i] = cs[i*2+1];
  }
  return cs2;
}
std::string findLongestPalindrome(std::string s) {
  if(s.length() == 0)
    return "";
  std::vector<char> temp(s.begin(),s.end());
  std::vector<char> s2 = addBoundaries(temp);
  std::vector<int> p(s2.size());
  int c = 0, r = 0; // Here the first element in s2 has been processed.
  int m = 0, n = 0; // The walking indices to compare if two elements are the same
  for(int i = 1; i < s2.size(); i++) {
    if(i > r) {
      p[i] = 0;
      m = i - 1;
      n = i + 1;
    }
    else {
      int i2 = c * 2 - i;
      if(p[i2] < (r - i)) {
        p[i] = p[i2];
        m = -1; // This signals bypassing the while loop below. 
      }
      else {
        p[i] = r - i;
        n = r + 1;
        m = i * 2 -n;
      }
    }
    while(m >= 0 && n < s2.size() && s2[m] == s2[n]){
      p[i]++;
      m--;
      n++;
    }
    if((i+p[i]) > r) {
      c = i;
      r = i + p[i];
    }
  }
  int len = 0;
  c = 0;
  for(int i = 1; i < s2.size(); ++i) {
    if(len < p[i]) {
      len = p[i];
      c = i;
    }    
  }
  std::vector<char> temp1(s2.begin() + (c - len), s2.begin() + (c + len + 1));
  std::vector<char> ss = removeBoundaries(temp1);
  return std::string(ss.begin(), ss.end());
}

Java implementacija

import java.util.Arrays;

public class ManachersAlgorithm {
    
    public static String findLongestPalindrome(String s) {
        if (s==null || s.length()==0)
            return "";
        
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length]; 
        int c = 0, r = 0; // Here the first element in s2 has been processed.
        int m = 0, n = 0; // The walking indices to compare if two elements are the same
        for (int i = 1; i<s2.length; i++) {
            if (i>r) {
                p[i] = 0; m = i-1; n = i+1;
            } else {
                int i2 = c*2-i;
                if (p[i2]<(r-i)) {
                    p[i] = p[i2];
                    m = -1; // This signals bypassing the while loop below. 
                } else {
                    p[i] = r-i;
                    n = r+1; m = i*2-n;
                }
            }
            while (m>=0 && n<s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
            }
            if ((i+p[i])>r) {
                c = i; r = i+p[i];
            }
        }
        int len = 0; c = 0;
        for (int i = 1; i<s2.length; i++) {
            if (len<p[i]) {
                len = p[i]; c = i;
            }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
    }
 
    private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
            return "||".toCharArray();

        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i<(cs2.length-1); i = i+2) {
            cs2[i] = '|';
            cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
    }

    private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length<3)
            return "".toCharArray();

        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i<cs2.length; i++) {
            cs2[i] = cs[i*2+1];
        }
        return cs2;
    }    
}

Literatura

• Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), „Paralelna detekcija svih palindroma u stringu”, Theoretical Computer Science, 141 (1–2): 163—173, doi:10.1016/0304-3975(94)00083-U .
• Crochemore, Maxime; Rytter, Wojciech (1991), „Korisnost upotrebe Karp-Miler-Rozenberg algoritma u paralelnim izračunavanjima na stringovima i nizovima”, Theoretical Computer Science, 88 (1): 59—82, MR 1130372, doi:10.1016/0304-3975(91)90073-B .
• Crochemore, Maxime; Rytter, Wojciech (2003), „8.1 Searching for symmetric words”, Dragulji stringologije: Algoritmi teksta, World Scientific, str. 111—114, ISBN 978-981-02-4897-0 .
• Gusfield, Dan (1997), „9.2 Finding all maximal palindromes in linear time”, Algoritmi na stringovima, stablima i sekvencama, Cambridge: Cambridge University Press, str. 197—199, ISBN 978-0-521-58519-4, MR 1460730, doi:10.1017/CBO9780511574931 .
• Jeuring, Johan (1994), „Izvođenje onlajn algoritama sa upotrebom za nalaženje palindroma”, Algorithmica, 11 (2): 146—184, MR 1272521, doi:10.1007/BF01182773 .
• Manacher, Glenn (1975), „"Onlajn" algoritam sa linearnim vremenom izvršavanja za nalaženje inicijalnog najmanjeg palindroma u stringu”, Journal of the ACM, 22 (3): 346—351, doi:10.1145/321892.321896 .

Spoljašnje veze

• Nalaženje najdužeg palindroma u stringu., 20. 11. 2011, Arhivirano iz originala 02. 02. 2014. g., Pristupljeno 24. 01. 2015 . Opis Manakerovog algoritma, sa linearnim vremenom izvršavanja, za nalaženje najdužeg palindroma u stringu
• Akalin, Fred (2007), Nalaženje najdužeg palindroma u stringu, u linearnom vremenu, Pristupljeno 22. 11. 2011 . Objašnjenje i implementacija u Pajtonu Manakerovog algoritma sa linearnom vremenskom složenošću.
• Žuring, Johan (2007—2010), Palindromi, Pristupljeno 22. 11. 2011 . Implementacija Žuringovog linearnog algoritma u Haskelu.
• Palindromi . Java implementacija Manakerovog algoritma.

Ovaj članak sadrži Longest palindromic substring na PEGWiki pod “Creative Commons Attribution” (CC-BY-3.0) licencom.