Manakers algoritm

Manakers algoritm
ändamål	Sök efter subpalindromer
Datastruktur	Linje
värsta tiden	$På)$
Minneskostnad	$På)$

Manachers algoritm är en algoritm med linjär körtid som låter dig få information om alla palindromiska delsträngar av en given sträng i komprimerad form . Introducerad av Glenn Manaker 1975. Den initiala uppgiften som löstes av algoritmen var att hitta den minsta prefix-palindromen i en given sträng, men strukturen som erhålls som ett resultat av algoritmens funktion tillåter att lösa mer allmänna problem. Så, Manaker visade att algoritmen låter dig kontrollera om en sträng kan representeras i formen , där - någon sträng - är dess omkastning. 1995 påpekade Apostolico, Breslauer och Galil att Manakers algoritm inte bara hittar det kortaste palindromiska prefixet, utan också den maximala palindromradien för varje möjlig mittpunkt av en palindromisk delsträng. ${\displaystyle (\omega \omega ^{R})^{k))$ $\omega$ $\omega ^{R}$

Förklaring av problemet

Låt vara ett snöre . Dess omkastning är en sträng som består av samma tecken, men skriven i omvänd ordning. ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n))$ ${\displaystyle \omega ^{R}=\omega _{n}\dots \omega _{2}\omega _{1))$
En sträng kallas palindrom om , det vill säga om den läser samma från vänster till höger och från höger till vänster. $\omega$ ${\displaystyle \omega =\omega ^{R))$
Ett palindrom sägs vara även om det har en jämn längd och udda annars. Varje jämnt palindrom har formen , och ett udda palindrom har formen , där är en godtycklig karaktär. $\omega$ ${\displaystyle \omega =vv^{R))$ ${\displaystyle \omega =vav^{R))$ $a$
Strängen har en palindrom med jämn radie centrerad vid position om för . Följaktligen har strängen en palindrom med udda radie centrerad vid om för . $\omega$ $r$ $k$ ${\displaystyle \omega _{ki}=\omega _{k+i-1))$ $i=1,\dots ,r$ $r$ $k$ ${\displaystyle \omega _{ki}=\omega _{k+i))$ $i=1,\dots ,r$

En radie sägs vara maximal för en position om strängen inte har ett palindrom med en radie centrerad i samma position. $r$ $k$ $r+1$

Manakers algoritm låter dig hitta i linjär tid de maximala radierna för jämna och udda palindromer vid varje position av strängen . $k=1,\prickar ,n$ $\omega$

Implementering

Nedan är implementeringen av algoritmen i Python .

def manager_odd ( s ): s = '$' + s + '^' n = len ( s ) res = [ 0 ] * n l = 0 r = 0 för i inom intervallet ( 1 , n - 1 ): res [ i ] = max ( 0 , min ( r - i , res [ l + ( r - i )])) medan s [ i - res [ i ]] == s [ i + res [ i ]]: res [ i ] += 1 om i + res [ i ] > r : l = i - res [ i ] r = i + res [ i ] returnera res [ 1 : - 1 ] def manacher ( s ): res = manacher_odd ( '#' + '#' . join ( s ) + '#' )[ 1 : -1 ] return ( [ x // 2 för x i res [:: 2 ]] , [ x // 2 för x i res [ 1 :: 2 ]])

Funktionen manacher_oddreturnerar en Manaker-matris för palindromer med udda längd, funktionen manacherreturnerar ett par Manaker-matriser för palindromer med udda respektive jämna längder, vilket reducerar beräkningen av en matris för jämna längder till ett udda fall genom att lägga till ett servicetecken #.

Litteratur

Manacher G. K. En ny linjär-tid "on-line" algoritm för att hitta den minsta initiala palindromen av en sträng // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1975. - Vol. 22, Iss. 3. - s. 346-351. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Parallell detektering av alla palindromer i en sträng (engelska) // Theoretical Computer Science - Elsevier BV , 1995. - Vol. 141, Iss. 1-2. - S. 163-173. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(94)00083-U

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likhet
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen