Pisin palindromi-alijono etsiminen
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16.7.2020 tarkistetusta
versiosta . tarkastukset vaativat
2 muokkausta .
Tietojenkäsittelytieteessä pisin palindrominen osamerkkijono - ongelma on ongelma löytää pisin osamerkkijonosta , joka on palindromi . Esimerkiksi "banaanin" pisin palindrominen osajono on "anana". Pisin palindrominen osajono ei välttämättä ole ainutlaatuinen; esimerkiksi merkkijonossa "abracadabra" ei ole palindromista osamerkkijonoa, joka on pidempi kuin kolme merkkiä, vaan on sellaisia, jotka koostuvat täsmälleen kolmesta merkistä, nimittäin "aka" ja "ada". Jotkut sovellukset haluavat löytää kaikki maksimaaliset palindromiset osamerkkijonot (eli kaikki alimerkkijonot, jotka ovat itse palindromeja ja joita ei voida täyttää pidempiin palindromisiin alimerkkijonoihin) sen sijaan, että palautettaisiin vain yksi osamerkkijono tai palindromisen osamerkkijonon enimmäispituus.
Manacher (1975 ) keksi aikalineaarisen algoritmin luettelemaan kaikki palindromit tietyn merkkijonon alussa. Kuitenkin, kuten Apostolico, Breslauer & Galil (1995 ) osoittavat, samaa algoritmia voidaan käyttää kaikkien pisimpien palindromisten alijonojen löytämiseen mistä tahansa annetusta merkkijonosta, jälleen lineaarisessa ajassa. Siksi se tarjoaa ratkaisun ongelmaan löytää suurin palindromiosamerkkijono lineaarisessa ajassa. Vaihtoehtoisia lineaarisia aikaratkaisuja ovat ehdottaneet Jeuring (1994 ) ja Gusfield (1997 ), jotka kuvasivat ratkaisun, joka perustuu päätepuiden käyttöön . Tehokkaat rinnakkaisalgoritmit tämän ongelman ratkaisemiseksi tunnetaan myös. [yksi]
Pisimmän palindromisen alijonon löytämisen ongelmaa ei pidä sekoittaa pisimmän palindromisen osajonon löytämisen ongelmaan .
Manakerin algoritmi
Löytääkseen pisimmän palindromin merkkijonosta lineaarisessa ajassa algoritmi voi käyttää seuraavia palindromien ja alipalindromien ominaisuuksia:
- Palindromin vasen puoli on sen oikean puolen peilikuva.
- (Tapaus 1) Kolmannella palindromilla, jonka keskipiste on ensimmäisen palindromin oikealla puolella, on täsmälleen sama pituus kuin toisella palindromilla, jonka keskipiste peilataan vasemmalle puolelle, jos toinen palindromi sijaitsee ensimmäisen sisällä ja vetäytyy rajalta ainakin yhdelle hahmolle.
- (Tapaus 2) Jos toisella palindromilla on yhteinen raja ensimmäisen palindromin kanssa tai se ulottuu sen yli, niin kolmannen palindromin pituus on taatusti vähintään etäisyys sen keskustasta ensimmäisen palindromin oikeaan reunaan. Tämä pituus on etäisyys toisen palindromin keskustasta ensimmäisen palindromin vasemmanpuoleiseen merkkiin.
- Kolmannen palindromin pituuden löytämiseksi tapauksessa 2, on tarpeen verrata ensimmäisen palindromin oikeanpuoleisimman merkin jälkeen olevia merkkejä peilikuvaansa kolmannen palindromin keskustasta, kunnes joko merkkijono on kulunut loppuun tai hahmoja löytyy.
- (Tapaus 3) Ensimmäinen tai toinen palindromi eivät anna tietoa sellaisen neljännen palindromin pituuden määrittämiseksi, jonka keskipiste on ensimmäisen palindromin rajan ulkopuolella.
- Siksi merkkijonon alimerkkijonojen palindromipituuksien määrittämiseksi vasemmalta oikealle on toivottavaa, että sinulla on viitepalindromi (toimii ensimmäisenä palindromina), jonka merkit ovat merkkijonon oikeanpuoleisimmilla paikoilla (ja siten kolmas palindromi tapauksessa 2 ja neljäs palindromi tapauksessa 3 voi korvata ensimmäisen palindromin, jolloin siitä tulee uusi vertailupalindromi).
- Mitä tulee ajan arvioimiseen merkkijonon kunkin merkin palindromipituuden määrittämiseen: tapauksessa 1 merkkien vertailua ei tehdä, tapauksissa 2 ja 3 vain ne merkkijonon merkit, jotka ovat viitepalindromin oikeanpuoleisimman merkin takana, ovat ehdokkaita. vertailu (ja siksi tapaus 3 johtaa aina muutokseen vertailupalindromissa, kun tapaus 2 muuttaa vertailupalindromia vain, jos käy ilmi, että kolmannen palindromin pituus on itse asiassa suurempi kuin sen luvattu vähimmäispituus).
- Parillisen asteen palindromeille keskus on palindromin kahden keskisymbolin välissä.
Toteutus
Päästää:
- s on N merkin merkkijono
- s2 on s:stä johdettu merkkijono, joka koostuu N * 2 + 1 elementistä, ja jokainen elementti vastaa yhtä seuraavista: N merkkiä s:ssä, N-1 välilyöntiä merkkien ja rajojen välillä sekä välilyönnit ennen ensimmäistä ja viimeistä merkkiä merkkijono s vastaavasti
- S2:n rajat eivät eroa palindromin pituuden löytämisessä
- Olkoon p palindromisäteiden joukko, eli etäisyys keskustasta mihin tahansa palindromin kaukaisimmasta merkistä (eli palindromin, jonka pituus on 3, palindromisäde on 1)
- Olkoon c sen palindromin keskipisteen sijainti, joka sisältää lähinnä s2:n oikeaa päätä olevan merkin (tämän palindromin pituus on p[c]*2+1)
- Olkoon r tämän palindromin oikeanpuoleisimman rajan sijainti (eli r = c + p[c])
- Olkoon i sen elementin (eli välilyönnin tai merkin) sijainti s2:ssa, jonka palindrominen säde määritetään, ja i on aina c:n oikealla puolella
- Olkoon i_mir i:n peilikuva c:n suhteen (eli {i, i_mir} = {6, 4}, {7, 3}, {8, 2},… kun c = 5 (siis, i_mir = c * 2 - i))
Tulos: Pisin palindromi eli merkkijonon ensimmäinen merkki
#sisällytä <merkkijono>
#sisällytä <vektori>
käyttäen nimiavaruutta std ;
string longestPalindromi ( const string & s ){
vektori < char > s2 ( s . koko ( ) * 2 + 1 , '#' );
//luo pseudomerkkijono, jonka #-raja
on ( int i = 0 ; i != s . size (); ++ i ){
s2 [ i * 2 + 1 ] = s [ i ];
}
intp [ s2 . _ koko ()];
int r , c , indeksi , i_mir ;
int maxLen = 1 ;
i_mir = indeksi = r = c = 0 ;
for ( int i = 1 ; i != s2 . koko () - 1 ; ++ i ){
i_mir = 2 * c - i ;
//Jos osumme edellisen tuloksen säteeseen,
//niin nykyisen säteen alkuarvo voidaan ottaa peilituloksesta p [ i ] = r > i ? min ( p [ i_mir ], r - i ) : 0 ;
while ( i > p [ i ] && ( i + p [ i ] + 1 ) < s2 . koko ( ) && 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 ];
indeksi = i ;
}
}
//Yhdistä löydetyt paikat alkuperäiseen merkkijonon
palautukseen s . substr (( indeksi - maxLen ) / 2 , maxLen );
}
Muistiinpanot
- ↑ Crochemore & Rytter (1991 ), Apostolico, Breslauer & Galil (1995 ).
Kirjallisuus
- Apostolico, Alberto; Breslauer, Dany & Galil, Zvi (1995), Parallel detection of all palindromes in a string , Theoretical Computer Science osa 141 (1–2): 163–173 , DOI 10.1016/0304-3975(94)00083-U .
- Crochemore, Maxime & Rytter, Wojciech (1991), Karp–Miller–Rosenberg-algoritmin käyttökelpoisuus merkkijonojen ja taulukoiden rinnakkaisissa laskelmissa , Theoretical Computer Science osa 88 (1): 59–82 , DOI 10.1016/0304-397 )90073-B .
- Crochemore, Maxime & Rytter, Wojciech (2003), 8.1 Symmetristen sanojen etsiminen, Jalokivet Stringology: Text Algorithms , World Scientific, s. 111–114, ISBN 978-981-02-4897-0 .
- Gusfield, Dan (1997), 9.2 Finding all maksimaaliset palindromit lineaarisessa ajassa , Algorithms on Strings, Trees, and Sequences , Cambridge: Cambridge University Press, s. 197–199, ISBN 0-521-58519-8 , DOI 10.1017/CBO9780511574931 .
- Jeuring, Johan (1994), On-line-algoritmien johtaminen, sovellus palindromien löytämiseen , Algorithmica osa 11 (2): 146–184 , DOI 10.1007/BF01182773 .
- Manacher, Glenn (1975), Uusi lineaariaikainen "on-line"-algoritmi merkkijonon pienimmän alkupalindromin löytämiseksi , Journal of the ACM , osa 22 (3): 346–351 , DOI 10.1145/321892.321896 .
Linkit
Tämä artikkeli sisältää tekstiä PEGWikin pisimmästä
palindromisesta osamerkkijonosta Creative Commons Attribution (
CC-BY-3.0 ) -lisenssillä.