Hledání nejdelšího podřetězce palindromu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. července 2020; kontroly vyžadují 2 úpravy .

V informatice je nejdelším palindromickým podřetězcem problém najít nejdelší podřetězec daného řetězce, kterým je palindrom .. Například nejdelší palindromický podřetězec „banánu“ je „anana“. Nejdelší palindromický podřetězec není nutně jedinečný; například v řetězci "abracadabra" není žádný palindromický podřetězec delší než tři znaky, ale existují řetězce skládající se přesně ze tří znaků, a to "aka" a "ada". Některé aplikace chtějí najít všechny maximální palindromické podřetězce (jmenovitě všechny podřetězce, které jsou samy palindromy a nelze je doplnit delšími palindromickými podřetězci) namísto vracení pouze jednoho podřetězce nebo vracení maximální délky palindromického podřetězce.

Manacher (1975 ) vynalezl časově lineární algoritmus pro výčet všech palindromů na začátku daného řetězce. Jak však ukázali Apostolico, Breslauer & Galil (1995 ), stejný algoritmus lze použít k nalezení všech nejdelších palindromických podřetězců kdekoli v daném řetězci, opět v lineárním čase. Proto poskytuje řešení problému nalezení maximálního palindromického podřetězce v lineárním čase. Alternativní řešení lineárního času navrhli Jeuring (1994 ) a Gusfield (1997 ), kteří popsali řešení založené na použití příponových stromů . Jsou také známy účinné paralelní algoritmy pro řešení tohoto problému. [jeden]

Problém nalezení nejdelší palindromické podřetězce by neměl být zaměňován s problémem nalezení nejdelší palindromické podsekvence .

Manažerův algoritmus

K nalezení nejdelšího palindromu v řetězci v lineárním čase může algoritmus použít následující vlastnosti palindromů a subpalindromů:

Levá strana palindromu je zrcadlovým obrazem jeho pravé strany.
(Případ 1) Třetí palindrom, jehož střed leží na pravé straně prvního palindromu, bude mít přesně stejnou délku jako druhý palindrom, jehož střed je zrcadlen na levou stranu, pokud druhý palindrom leží uvnitř prvního palindromu a vzdaluje se od hranice v bodě alespoň pro jednu postavu.
(Případ 2) Pokud má druhý palindrom společnou hranici s prvním palindromem nebo ji přesahuje, pak je zaručeno, že délka třetího palindromu nebude menší než vzdálenost od jeho středu k pravému okraji prvního palindromu. Tato délka je vzdálenost od středu druhého palindromu k levému znaku prvního palindromu.
Abychom našli délku třetího palindromu v případě 2, je nutné porovnat znaky následující za znakem úplně vpravo prvního palindromu s jejich zrcadlovým obrazem kolem středu třetího palindromu, dokud není řetězec vyčerpán nebo nerovnost znaky jsou nalezeny.
(Případ 3) První ani druhý palindrom neposkytuje informace pro určení délky čtvrtého palindromu, jehož střed leží mimo hranici prvního palindromu.
Proto je pro určení palindromických délek podřetězců v řetězci zleva doprava žádoucí mít referenční palindrom (fungující jako první palindrom), jehož znaky zaujímají v řetězci pozice úplně vpravo (a tedy třetí palindrom v případě 2). a čtvrtý palindrom v případě 3 může nahradit první palindrom, aby se stal novým referenčním palindromem).
Pokud jde o odhad času pro určení palindromické délky pro každý znak řetězce: v případě 1 se neprovádí žádné porovnání znaků, v případech 2 a 3 jsou kandidáty na znak pouze znaky řetězce ležící za znakem zcela vpravo referenčního palindromu. srovnání (a proto Případ 3 vždy vede ke změně referenčního palindromu, když Případ 2 změní referenční palindrom pouze v případě, že se ukáže, že délka třetího palindromu je ve skutečnosti větší než jeho slíbená minimální délka).
U palindromů sudého stupně leží střed mezi dvěma středovými symboly palindromu.

Implementace

Nechat:

s je řetězec N znaků
s2 je řetězec odvozený od s, který se skládá z N * 2 + 1 prvků, přičemž každý prvek odpovídá jednomu z: N znaků v s, N-1 mezer mezi znaky a hranicemi a mezer před prvním a za posledním znakem řetězec s resp
Hranice v s2 se neliší, pokud jde o nalezení délky palindromu
Nechť p je pole poloměrů palindromu, tj. vzdálenost od středu k libovolnému z nejvzdálenějších znaků palindromu (tj. palindrom délky 3 má palindromický poloměr 1)
Nechť c je poloha středu palindromu obsahujícího znak nejblíže pravému konci s2 (délka tohoto palindromu je p[c]*2+1)
Nechť r je poloha pravé krajní hranice tohoto palindromu (tj. r = c + p[c])
Nechť i je poloha prvku (tj. mezery nebo znaku) v s2, jehož palindromický poloměr se určuje, přičemž i je vždy umístěno vpravo od c
Nechť i_mir je zrcadlový obraz i vzhledem k c (tj. {i, i_mir} = {6, 4}, {7, 3}, {8, 2},… když c = 5 (proto i_mir = c *2 – i))

Výsledek: Nejdelší palindrom nebo první znak řetězce

#include <řetězec> #include <vektor> pomocí jmenného prostoru std ; string longestPalindrome ( const string & s ){ vektor < char > s2 ( velikost s . () * 2 + 1 , '#' ); //vytvoří pseudo-řetězec s hranicemi '#' pro ( int i = 0 ; i != s . velikost (); ++ i ){ s2 [ i * 2 + 1 ] = s [ i ]; } intp [ s2 . _ velikost ()]; int r , c , index , i_mir ; int maxLen = 1 ; i_mir = index = r = c = 0 ; for ( int i = 1 ; i != s2 . velikost ( ) - 1 ; ++ i ){ i_mir = 2 * c - i ; //Pokud spadáme do poloměru předchozího výsledku, //pak lze počáteční hodnotu aktuálního poloměru vzít ze zrcadleného výsledku p [ i ] = r > i ? min ( p [ i_mir ], r - i ) : 0 ; while ( i > p [ i ] && ( i + p [ i ] + 1 ) < s2 . velikost () && s2 [ i - p [ i ] - 1 ] == s2 [ i + p [ i ] + 1 ] ) ++ p [ i ]; if ( p [ i ] + i > r ){ c = i ; r = i + p [ i ]; } if ( maxLen < p [ i ]){ maxLen = p [ i ]; index = i ; } } //Namapujte nalezené pozice na původní řetězec return s . substr (( index - maxLen ) / 2 , maxLen ); }

Poznámky

↑ Crochemore & Rytter (1991 ), Apostolico, Breslauer & Galil (1995 ).

Literatura

Apostolico, Alberto; Breslauer, Dany & Galil, Zvi (1995), Paralelní detekce všech palindromů v řetězci , Theoretical Computer Science vol. 141 (1–2): 163–173 , DOI 10.1016/0304-3975(94)00083-U .
Crochemore, Maxime & Rytter, Wojciech (1991), Užitečnost algoritmu Karp–Miller–Rosenberg v paralelních výpočtech na řetězcích a polích , Theoretical Computer Science vol. 88 (1): 59–82 , DOI 10.1016/0304-3975 (91 )90073-B .
Crochemore, Maxime & Rytter, Wojciech (2003), 8.1 Hledání symetrických slov, Klenoty stringologie: Textové algoritmy , World Scientific, s. 111–114, ISBN 978-981-02-4897-0 .
Gusfield, Dan (1997), 9.2 Hledání všech maximálních palindromů v lineárním čase , Algorithms on Strings, Trees, and Sequences , Cambridge: Cambridge University Press, str. 197–199, ISBN 0-521-58519-8 , DOI 10.1017/CBO9780511574931 .
Jeuring, Johan (1994), The derivation of on-line algorithms, with application to find palindromes , Algorithmica vol . 11 (2): 146–184 , DOI 10.1007/BF01182773 .
Manacher, Glenn (1975), Nový lineární "on-line" algoritmus pro nalezení nejmenšího počátečního palindromu řetězce , Journal of the ACM vol. 22 (3): 346–351 , DOI 10.1145/321892.321896 .

Odkazy

Nejdelší palindromický podřetězec část II. , 2011-11-20 , < http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html > Archivováno2. února 2014 naWayback Machine. Popis Manacherova algoritmu pro nalezení nejdelšího palindromického podřetězce v lineárním čase.
Akalin , Fred (2007), Hledání nejdelšího palindromického podřetězce v lineárním čase , . Staženo 22. listopadu 2011. . Vysvětlení a implementace manažerského lineárního algoritmu v Pythonu.
Jeuring, Johan (2007–2010), Palindromes , < http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/index.html > . Staženo 22. listopadu 2011. . Haskell implementace Jeuringova lineárního algoritmu.
Palindromes , < https://github.com/vvikas/palindromes/blob/master/src/LongestPalindromicSubString.java > (mrtvý odkaz). Java implementace Manažerova lineárního algoritmu.

Tento článek zahrnuje text z Longest palindromického podřetězce na PEGWiki pod licencí Creative Commons Attribution ( CC-BY-3.0 ).