A leghosszabb palindrom részkarakterlánc megkeresése

A számítástechnikában a leghosszabb palindrom részkarakterlánc  -probléma egy adott karakterlánc leghosszabb, palindrom részstringjének megtalálása . Például a "banán" leghosszabb palindrom részlánca az "anana". A leghosszabb palindrom részkarakterlánc nem feltétlenül egyedi; például az "abracadabra" karakterláncban nincs három karakternél hosszabb palindrom részkarakterlánc, de vannak olyanok, amelyek pontosan három karakterből állnak, nevezetesen az "aka" és az "ada". Egyes alkalmazások meg akarják találni az összes maximális palindrom részkarakterláncot (nevezetesen az összes olyan részstringet, amely önmagukban palindrom, és nem tölthető ki hosszabb palindrom részkarakterláncokhoz), ahelyett, hogy csak egy részkarakterláncot adna vissza, vagy egy palindrom részkarakterlánc maximális hosszát.

Manacher (1975 ) feltalált egy idő-lineáris algoritmust, amely egy adott karakterlánc elején lévő összes palindromot felsorolja. Azonban, amint azt Apostolico, Breslauer és Galil (1995 ) kimutatta, ugyanaz az algoritmus használható az összes leghosszabb palindrom részstring megtalálására egy adott karakterláncban bárhol, ismét lineáris időben. Ezért megoldást ad arra a problémára, hogy lineáris időben megtaláljuk a maximális palindrom részstringet. Alternatív lineáris időmegoldásokat javasoltak Jeuring (1994 ) és Gusfield (1997 ), akik utótagfák használatán alapuló megoldást írtak le . A probléma megoldására hatékony párhuzamos algoritmusok is ismertek. [egy]

A leghosszabb palindrom részsorozat megtalálásának problémáját nem szabad összetéveszteni a leghosszabb palindrom részsorozat megtalálásának problémájával .

Menedzser algoritmusa

Egy karakterlánc leghosszabb palindromának lineáris időben történő megtalálásához az algoritmus a palindromok és szubpalindromok következő tulajdonságait használhatja:

1. A palindrom bal oldala a jobb oldalának tükörképe.
2. (1. eset) Egy harmadik palindrom, amelynek középpontja az első palindrom jobb oldalán van, pontosan akkora hosszú lesz, mint a második palindromé, amelynek középpontja a bal oldalra tükröződik, ha a második palindrom az elsőn belül helyezkedik el, és távolodik a határtól legalább egy karakterre.
3. (2. eset) Ha a második palindromnak közös határa van az első palindrommal, vagy túlnyúlik azon, akkor a harmadik palindrom hossza garantáltan nem lesz kisebb, mint a középpontja és az első palindrom jobb határa közötti távolság. Ez a hosszúság a második palindrom középpontja és az első palindrom bal szélső karaktere közötti távolság.
4. A harmadik palindrom hosszának meghatározásához a 2. esetben össze kell hasonlítani az első palindrom jobb szélső karakterét követő karaktereket a harmadik palindrom középpontjának tükörképével mindaddig, amíg vagy a karakterlánc ki nem merül, vagy a karakterek találhatók.
5. (3. eset) Sem az első, sem a második palindrom nem ad információt egy negyedik palindrom hosszának meghatározásához, amelynek középpontja az első palindrom határán kívül van.
6. Ezért a karakterláncban lévő részkarakterláncok palindrom hosszának balról jobbra történő meghatározásához kívánatos egy referencia palindrom (amely az első palindromként működik), amelynek karakterei a karakterlánc jobb szélső pozícióját foglalják el (és így a harmadik palindrom a 2. esetben és a negyedik palindrom a 3. esetben helyettesítheti az első palindromot, és az új referencia palindrommá válik).
7. A karakterlánc egyes karaktereinél a palindrom hossz meghatározásához szükséges idő becslésével kapcsolatban: az 1. esetben nem történik karakter-összehasonlítás, a 2. és 3. esetben csak a referencia palindrom jobb szélső karakterén túl eső karakterláncok a jelöltek. összehasonlítás (és ezért a 3. eset mindig a referencia palindrom változásához vezet, amikor a 2. eset csak akkor változtatja meg a referencia palindromot, ha kiderül, hogy a harmadik palindrom hossza valójában nagyobb, mint az ígért minimális hossz).
8. A páros fokú palindromok középpontja a palindrom két középső szimbóluma között helyezkedik el.

Megvalósítás

Legyen:

• s egy N karakterből álló sztring
• Az s2 egy s-ből származó karakterlánc, amely N * 2 + 1 elemből áll, és minden elem megfelel a következők egyikének: N karakter az s-ben, N-1 szóköz a karakterek és határok között, valamint szóköz az első és az utolsó karakter után a string s ill
• Az s2 korlátok nem különböznek a palindrom hosszának meghatározásában
• Legyen p a palindrom sugarainak tömbje, azaz a középpont és a palindrom bármely legtávolabbi karakterének távolsága (azaz egy 3 hosszúságú palindrom sugara 1)
• Legyen c az s2 jobb végéhez legközelebb eső karaktert tartalmazó palindrom középpontja (ennek a palindromnak a hossza p[c]*2+1)
• Legyen r ennek a palindromnak a jobb szélső határának helyzete (azaz r = c + p[c])
• Legyen i annak az elemnek (azaz szóköznek vagy karakternek) a helyzete s2-ben, amelynek palindrom sugarát meghatározzuk, és i mindig a c jobb oldalán helyezkedik el.
• Legyen i_mir i tükörképe c-hez képest (azaz {i, i_mir} = {6, 4}, {7, 3}, {8, 2},… ha c = 5 (tehát i_mir = c * 2 - i))

Eredmény: A leghosszabb palindrom vagy a karakterlánc első karaktere