Проблем најдужег палиндрома у стрингу

У информатици, проблем најдужег палиндрома у стрингу или највећи симетрични фактор је проблем налажења најдужег подстринга датог стринга, подстринг мора бити палиндром. На пример, најдужи палиндром у речи "банана" је "анана". Најдужи палиндром не мора бити јединствен; на пример, у стрингу "абракадабра", не постоји палиндром који има више од три слова, али постоје два палиндрома са дужином три, конкретно, "ака" и "ада". У неким применама је потребно вратити све највеће палиндроме (односно, све подстрингове који су палиндроми и не могу бити проширени а да притом задрже својство палиндрома) уместо враћања само једног од најдужих палиндрома или дужине највећег палиндрома у оквиру стринга..

Глен Манакер 1975 је нашао алгоритам у линеарном времену за листање свих палиндрома који се појављују на почетку стринга. Међутим, Apostolico, Breslauer & Galil 1995, су приметили да се исти алгоритам може употребити за налажење највећих палиндрома у стрингу, небитно од позиције палиндрома, опет у линеарном времену. Дакле, пружа решење на проблем налажења најдужег палиндрома у стрингу у линеарном времену. Алтернативно решење које се такође извршава у линеарном времену су пружили Jeuring 1994 и Gusfield 1997, који су описали решење засновано на суфиксном стаблу. Познат је и ефикасни паралелни алгоритам за овај проблем.^[1]

Најдужи палиндром у стрингу не сме бити помешан са другим проблемом налажења најдужег подскупа који задовољава својство палиндрома. Подскуп стринга иако задовољава својство, у опису проблема, да се карактери појављују у растућем редоследу (у смислу први члан подскупа се сигурно појављује пре другог и тако редом) не подразумева се да су чланови подскупа УЗАСТОПНИ, што је услов код најдужег палиндрома у стрингу.

Манакеров алгоритам

Да би нашли у линеарном времену најдужи палиндром у стрингу, алгоритам користи одређене карактеристике и закључке о палиндромима и под-палиндормима (у овом контексту палиндром са тенденцијом раста, на пример реч "ада" може се проширити у "радар"):

Лева страна палиндрома је десне страна "у огледалу" (односно када би почели са почетка леве и краја десне стране и итерирали ка унутра слова кроз која би пролазили би била иста).
Термин у огледалу ћемо користити да обележимо карактер који се налази на позицији која удаљена од десног краја исто онолико колико је позиција тренутног карактера удаљена од левог краја, под условом да је карактер ближи десном крају палиндрома, у супротном је ситуација обрнута.
(Случај 1) Ако трећи палиндром чији је центар у оквиру десне стране првог палиндрома ће имати тачно исту дужину као и други палиндром који почиње са места које је "у огледалу" у односу на почетак трећег палиндрома ако је други палиндром у оквиру граница првог палиндрома, са одступањем за најмање један карактер.
(Случај 2) Ако други палиндром додирује или се простире ван леве границе првог палиндрома онда је трећи палиндром гарантавано најмању дужину која износи дужину од сопственог центра до највише десног карактера првог палиндрома. Ова дужина је иста као и дужина од центра другог палиндрома до највише левог карактера првог палиндрома.
Да би нашли дужину трећег палиндрома из случаја 2, следећи карактер после највише десног карактера првог палиндрома би требало да буде поређен са његовим "одразом у огледалу" од центра трећег палиндром, док се не поклопе карактери или нема више карактера за поређење.
(Случај 3) Ни први ни други палиндром не пружају информација које би помогле да се одреди дужина четвртог палиндрома чији је центар изван десне стране првог палиндрома.
Дакле пожељно би било да имамо палиндром као референцу (односно улогу првог палиндрома) који поседује карактере најдаље десно у стрингу, када налазимо слева ка десно дужину палиндрома у стрингу (и стога трећи палиндром у другом случају и четврти палиндром у трећем случају могу заменити први палиндром као нову референцу).
Што се тиче временске сложености налажења дужине палиндрома за сваки карактер у стрингу, не постоји поређење карактера за први случај, док за други и трећи само карактери у стрингу који се налазе изван највише десног каратера референтног палиндрома су кандидати за поређење (и стога трећи случај ће увек резултовати новим референтним (првим) палиндромом док други случај резултује новим референтним палиндромом само ако је трећи палиндром заправо дужи од гарантоване минималне дужине).
За палиндром парне дужине, центар је на граници два средња карактера

Имплементација

Нека је:

s је стринг од N карактера
s2 изведен стринг од s, који обухвата N * 2 + 1 елемената, где сваки елемент одговара једном од следећих случајева: N каратера у s, N-1 граница између карактера, и границе пре и после првог и последњег каратера респективно.
Граница у s2 је једнака било којој другој граници у s2 у погледу усклађености елемената у одређивању дужине палиндрома.
p низ палиндромских размака за сваки елемент у s2, од центра до било ког граничног елемента, где се свака граница урачунава у палиндром (то јест палиндром који има само три елемента има палиндромску дужину 1)
c је позиција центра палиндрома за који тренутно знамо да укључује границу најближу десном крају стринга s2 (то јест, дужина палиндрома = p[c]*2+1)
r је позиција највише десне границе овог палиндрома (то јест, r = c + p[c])
i је позиција елемента (то јест, карактер или граница) у s2 чија се палиндромска дужина одређује, притом је i увек десно од c
i2 је позиција у огледалу од i око c (то јест, {i, i2} = {6, 4}, {7, 3}, {8, 2},… када је c = 5 (то јест, i2 = c * 2 - i)

C++ имплементација

#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());
}

Јава имплементација

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;
    }    
}

Референце

^ Crochemore & Rytter 1991, Apostolico, Breslauer & Galil 1995

Литература

Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), „Паралелна детекција свих палиндрома у стрингу”, Theoretical Computer Science, 141 (1–2): 163—173, doi:10.1016/0304-3975(94)00083-U .
Crochemore, Maxime; Rytter, Wojciech (1991), „Корисност употребе Карп-Милер-Розенберг алгоритма у паралелним израчунавањима на стринговима и низовима”, 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”, Драгуљи стрингологије: Алгоритми текста, World Scientific, стр. 111—114, ISBN 978-981-02-4897-0 .
Gusfield, Dan (1997), „9.2 Finding all maximal palindromes in linear time”, Алгоритми на стринговима, стаблима и секвенцама, Cambridge: Cambridge University Press, стр. 197—199, ISBN 978-0-521-58519-4, MR 1460730, doi:10.1017/CBO9780511574931 .
Jeuring, Johan (1994), „Извођење онлајн алгоритама са употребом за налажење палиндрома”, Algorithmica, 11 (2): 146—184, MR 1272521, doi:10.1007/BF01182773 .
Manacher, Glenn (1975), „"Онлајн" алгоритам са линеарним временом извршавања за налажење иницијалног најмањег палиндрома у стрингу”, Journal of the ACM, 22 (3): 346—351, doi:10.1145/321892.321896 .

Спољашње везе

Налажење најдужег палиндрома у стрингу., 20. 11. 2011, Архивирано из оригинала 02. 02. 2014. г., Приступљено 24. 01. 2015 . Опис Манакеровог алгоритма, са линеарним временом извршавања, за налажење најдужег палиндрома у стрингу
Акалин, Фред (2007), Налажење најдужег палиндрома у стрингу, у линеарном времену, Приступљено 22. 11. 2011 . Објашњење и имплементација у Пајтону Манакеровог алгоритма са линеарном временском сложеношћу.
Журинг, Јохан (2007—2010), Палиндроми, Приступљено 22. 11. 2011 . Имплементација Журинговог линеарног алгоритма у Хаскелу.
Палиндроми ^{[мртва веза]}. Јава имплементација Манакеровог алгоритма.

Овај чланак садржи Longest palindromic substring на PEGWiki под “Creative Commons Attribution” (CC-BY-3.0) лиценцом.

[1] Crochemore & Rytter 1991, Apostolico, Breslauer & Galil 1995

[1]