Manakerin algoritmi

Manakerin algoritmi
tarkoitus	Etsi subpalindromeja
Tietorakenne	Linja
pahin aika	$Päällä)$
Muistin hinta	$Päällä)$

Manacherin algoritmi on algoritmi , jonka ajoaika on lineaarinen ja jonka avulla voit saada tietoa tietyn merkkijonon kaikista palindromisista osamerkkijonoista pakatussa muodossa . Esitteli Glenn Manaker vuonna 1975. Algoritmin ratkaisemana lähtötehtävänä oli löytää tietyn merkkijonon pienin etuliite-palindromi, mutta algoritmin toiminnan tuloksena saatu rakenne mahdollistaa yleisempien ongelmien ratkaisemisen. Joten Manaker osoitti, että algoritmin avulla voit tarkistaa, voidaanko merkkijono esittää muodossa , jossa - jokin merkkijono - on sen käänteinen. Vuonna 1995 Apostolico, Breslauer ja Galil huomauttivat, että Manakerin algoritmi ei vain löydä lyhimmän palindromisen etuliitettä, vaan myös löytää palindromin suurimman säteen kullekin mahdolliselle palindromisen osajonon keskipisteelle. $(\omega \omega ^{R})^{k}$ $\omega$ $\omega ^{R}$

Ongelman selvitys

Olkoon jokin merkkijono . Sen kääntö on merkkijono , joka koostuu samoista merkeistä, mutta kirjoitetaan käänteisessä järjestyksessä. ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n))$ ${\displaystyle \omega ^{R}=\omega _{n}\dots \omega _{2}\omega _{1))$
Merkkijonoa kutsutaan palindromiksi , jos , eli jos se lukee saman vasemmalta oikealle ja oikealta vasemmalle. $\omega$ ${\displaystyle \omega =\omega ^{R))$
Palindromin sanotaan olevan parillinen, jos sen pituus on parillinen ja muuten pariton . Jokaisella parillisella palindromilla on muoto , ja parittomalla palindromilla on muoto , jossa on mielivaltainen merkki. $\omega$ ${\displaystyle \omega =vv^{R))$ ${\displaystyle \omega =vav^{R))$ $a$
Merkkijonolla on parillinen sädepalindromi , joka on keskitetty kohtaan, jos for . Näin ollen merkkijonolla on pariton säde palindromi, jonka keskipisteenä on if for . $\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$

Säteen sanotaan olevan paikan maksimi , jos merkkijonossa ei ole palindromia, jonka säde on keskitetty samaan kohtaan. $r$ $k$ $r+1$

Manaker-algoritmin avulla voit löytää lineaarisessa ajassa parillisten ja parittomien palindromien enimmäissäteet merkkijonon kussakin kohdassa . $k=1,\pisteet ,n$ $\omega$

Toteutus

Alla on algoritmin toteutus Pythonissa .

def manager_odd ( s ): s = '$' + s + '^' n = len ( s ) res = [ 0 ] * n l = 0 r = 0 i :lle alueella ( 1 , n - 1 ) : res [ i ] = max ( 0 , min ( r - i , res [ l + ( r - i )])) kun taas s [ i - res [ i ]] == s [ i + res [ i ]]: res [ i ] ] += 1 jos i + res [ i ] > r : l = i - res [ i ] r = i + res [ i ] palauttaa res [ 1 : - 1 ] def manacher ( s ): res = manacher_odd ( '#' + '#' . join ( s ) + '#' )[ 1 : - 1 ] return ([ x // 2 for x in res [:: 2 ]] , [ x // 2 for x in res [ 1 :: 2 ]])

Funktio manacher_oddpalauttaa Manaker-taulukon parittoman pituisille palindromeille, funktio manacherpalauttaa parittoman ja parillisen pituisille palindromeille Manaker-taulukon, mikä vähentää parillisten pituuksien taulukon laskennan parittomaan tapaukseen lisäämällä palvelumerkin #.

Kirjallisuus

Manacher G. K. Uusi lineaariaikainen "on-line"-algoritmi merkkijonon pienimmän alkupalindromin löytämiseksi // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery , 1975. - Voi. 22, Iss. 3. - s. 346-351. — ISSN 0004-5411 ; 1557-735X - doi: 10.1145/321892.321896
Apostolico A. , Breslauer D., Galil Z. Kaikkien palindromien rinnakkaistunnistus merkkijonossa (englanniksi) // Theoretical Computer Science - Elsevier BV , 1995. - Voi. 141, Iss. 1-2. - s. 163-173. — ISSN 0304-3975 ; 1879-2294 - doi: 10.1016/0304-3975(94)00083-U

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
Muut	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono