Algoritmul lui Manaker

Algoritmul lui Manaker
scop	Căutați subpalindromuri
Structură de date	Linia
cel mai rău moment	$Pe)$
Costul memoriei	$Pe)$

Algoritmul lui Manacher este un algoritm cu timp de rulare liniar care vă permite să obțineți informații despre toate subșirurile palindromice ale unui șir dat într-o formă comprimată . Introdus de Glenn Manaker în 1975. Sarcina inițială rezolvată de algoritm a fost găsirea celui mai mic prefix-palindrom al unui șir dat, dar structura obținută ca urmare a funcționării algoritmului permite rezolvarea unor probleme mai generale. Deci, Manaker a demonstrat că algoritmul vă permite să verificați dacă un șir poate fi reprezentat sub forma , unde — un șir — este inversarea acestuia. În 1995, Apostolico, Breslauer și Galil au subliniat că, prin proiectare, algoritmul lui Manaker nu numai că găsește cel mai scurt prefix palindromic, dar găsește și raza maximă a palindromului pentru fiecare centru posibil al unui subșir palindromic. $(\omega \omega ^{R})^{k}$ $\omega$ $\omega ^{R}$

Enunțul problemei

Să fie o sfoară . Inversarea sa este un șir compus din aceleași caractere, dar scris în ordine inversă. $\omega =\omega _{1}\omega _{2}\dots \omega _{n)$ $\omega ^{R}=\omega _{n}\dots \omega _{2}\omega _{1)$
Un șir se numește palindrom dacă , adică dacă citește la fel de la stânga la dreapta și de la dreapta la stânga. $\omega$ $\omega =\omega ^{R)$
Se spune că un palindrom este par dacă are o lungime pară și, în caz contrar , impar . Orice palindrom par are forma , iar un palindrom impar are forma , unde este un caracter arbitrar. $\omega$ $\omega =vv^{R)$ $\omega =vav^{R)$ $A$
Coarda are un palindrom cu rază uniformă centrat pe poziție dacă pentru . În consecință, șirul are un palindrom cu rază impară centrat la dacă pentru . $\omega$ $r$ $k$ $\omega _{ki}=\omega _{k+i-1)$ $i=1,\dots ,r$ $r$ $k$ $\omega _{ki}=\omega _{k+i)$ $i=1,\dots ,r$

Se spune că o rază este maximă pentru o poziție dacă șirul nu are un palindrom cu o rază centrată în aceeași poziție. $r$ $k$ $r+1$

Algoritmul lui Manaker vă permite să găsiți în timp liniar razele maxime ale palindromurilor pare și impare la fiecare poziție a șirului . $k=1,\dots ,n$ $\omega$

Implementare

Mai jos este implementarea algoritmului în Python .

def manager_odd ( s ): s = '$' + s + '^' n = len ( s ) res = [ 0 ] * n l = 0 r = 0 pentru i în interval ( 1 , n - 1 ): res [ i ] = max ( 0 , min ( r - i , res [ l + ( r - i )])) în timp ce s [ i - res [ i ]] == s [ i + res [ i ]]: res [ i ] += 1 dacă i + res [ i ] > r : l = i - res [ i ] r = i + res [ i ] return res [ 1 : - 1 ] def manacher ( s ): res = manacher_odd ( '#' + '#' . join ( s ) + '#' )[ 1 : - 1 ] return ([ x // 2 pentru x în res [:: 2 ]] , [ x // 2 pentru x în res [ 1 :: 2 ]])

Funcția manacher_oddreturnează un tablou Manaker pentru palindromurile de lungime impară, funcția manacherreturnează o pereche de tablouri Manaker pentru palindromurile de lungimi impare și, respectiv, reducând calculul unui tablou pentru lungimi pare la un caz impar prin adăugarea unui caracter de serviciu #.

Literatură

Manacher G. K. Un nou algoritm „on-line” în timp liniar pentru găsirea celui mai mic palindrom inițial al unui șir // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1975. - Vol. 22, Iss. 3. - P. 346-351. — ISSN 0004-5411 ; 1557-735X - doi:10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Parallel detection of all palindromes in a string (engleză) // Theoretical Computer Science - Elsevier BV , 1995. - Vol. 141, Iss. 1-2. - P. 163-173. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(94)00083-U

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănarea Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun