Nejdelší palindromický podřetězec - Longest palindromic substring - Wikipedia

v počítačová věda, nejdelší palindromický podřetězec nebo nejdelší symetrický faktor problém je problém najít souvislou maximální délku podřetězec daného řetězce, který je také a palindrom. Například nejdelší palindromický podřetězec „banánů“ je „anana“. Nejdelší palindromický podřetězec není zaručeně jedinečný; například v řetězci „abracadabra“ není palindromický podřetězec s délkou větší než tři, ale existují dva palindromické podřetězce s délkou tři, a to „aca“ a „ada“. V některých aplikacích může být nutné vrátit všechny maximální palindromické podřetězce (tj. Všechny podřetězce, které jsou samy palindromy a nelze je rozšířit na větší palindromické podřetězce), místo aby vraceli pouze jeden podřetězec nebo vraceli maximální délku palindromického podřetězce.

Manacher (1975) vynalezl a lineární čas algoritmus pro výpis všech palindromů, které se objeví na začátku daného řetězce. Jak však bylo pozorováno např Apostolico, Breslauer & Galil (1995) Stejný algoritmus lze také použít k vyhledání všech maximálních palindromických podřetězců kdekoli ve vstupním řetězci, opět v lineárním čase. Proto poskytuje lineární časové řešení nejdelšího problému s palindromickým dílčím řetězcem. Alternativní lineární časová řešení poskytl Jeuring (1994), a tím Gusfield (1997), který popsal řešení založené na stromy přípon. Účinný paralelní algoritmy jsou také známé pro tento problém.[1]

Nejdelší palindromický podřetězcový problém by neměl být zaměňován s jiným problémem najít nejdelší palindromický subsekvence.

Manacherův algoritmus

Najít nejdelší palindrom v řetězci v lineární čas, algoritmus může využít následujících charakteristik nebo pozorování o palindromu a subpalindromu:

  1. Levá strana palindromu je zrcadlovým obrazem jeho pravé strany.
  2. (Případ 1) Třetí palindrom, jehož střed je na pravé straně prvního palindromu, bude mít přesně stejnou délku jako druhý palindrom ukotven ve středu zrcadla na levé straně, pokud je druhý palindrom v mezích prvního palindromu alespoň jedním znakem (nesplňuje levou hranici prvního palindromu). Například „dacabacad“ je celý řetězec prvním palindromem, „aca“ na levé straně druhým palindromem, „aca“ na pravé straně třetím palindromem. V tomto případě mají druhý a třetí palindrom přesně stejnou délku.
  3. (Případ 2) Pokud se druhý palindrom setká nebo přesahuje levou hranici prvního palindromu, pak je vzdálenost od středu druhého palindromu k levé hranici prvního palindromu přesně stejná jako vzdálenost od středu třetího palindrom k pravé hranici prvního palindromu.
  4. Chcete-li zjistit délku třetího palindromu v případě 2, další znak za pravým krajním znakem prvního palindromu by se poté porovnal se zrcadlovým znakem kolem středu třetího palindromu, dokud nebude shoda nebo žádné další znaky porovnat.
  5. (Případ 3) Ani první, ani druhý palindrom neposkytuje informace, které by pomohly určit palindromickou délku čtvrtého palindromu, jehož střed je mimo pravou stranu prvního palindromu.
  6. Je proto žádoucí mít jako referenci palindrom (tj. Roli prvního palindromu), který má znaky nejvzdálenější vpravo v řetězci při určování palindromické délky dílčího řetězce v řetězci zleva doprava (a následně třetí palindrom v případě 2 a čtvrtý palindrom v případě 3 by mohl nahradit první palindrom, aby se stal novou referencí).
  7. Pokud jde o časovou složitost stanovení palindromické délky pro každý znak v řetězci: pro případ 1 neexistuje srovnání znaků, zatímco pro případy 2 a 3 jsou kandidáty pro srovnání pouze znaky v řetězci za pravým vnějším znakem referenčního palindromu ( a následně případ 3 vždy vede k novému referenčnímu palindromu, zatímco případ 2 tak učiní pouze v případě, že třetí palindrom je ve skutečnosti delší než jeho zaručená minimální délka).
  8. U sudých palindromů je střed na hranici dvou znaků uprostřed.


Pseudo kód

    daný řetězec S řetězec S '= S s falešným znakem (např.' | ') vloženým mezi každý znak (včetně vnějších hranic) pole P = [0, ..., 0] // Uložení délek palindromu pro každý střed v S '// poznámka: délka (S') = délka (P) = 2 × délka (S) + 1 // Sledujte následující indexy do P nebo S 'R = 0 // Další prvek, který má být zkoumány; index do S C = 0 // Největší / nejvíce levý palindrom, jehož pravá hranice je R-1; index do S i = 1 // Další palindrom, který se má vypočítat; index do P definovat L = i - (R - i) // Kandidát znaků pro srovnání s R; index do S definovat i '= C - (i - C) // Palindromové zrcadlení i z C; index do P zatímco R Li i je v palindromu v C (případy 1 a 2): Nastavte P [i] = P [i '] // poznámka: vyvolání P je inicializováno na všech 0 s // Rozbalte palindrom v i (primárně případy 2 a 3; lze přeskočit v případě 1, // i když jsme již ukázali, že S '[R] ≠ S' [L], protože jinak by se palindrom // at i 'rozšířil alespoň k levému okraji palindromu v C) : zatímco S '[R] == S' [L]: přírůstek P [i] přírůstek R Li palindrom v bodě i přesahuje palindrom v bodě C: aktualizace C = i přírůstek i vrátit se max (P)

To se trochu liší od Manacherova původního algoritmu především záměrným prohlášením a fungováním R takovým způsobem, aby pomohl ukázat, že runtime je ve skutečnosti lineární. Na pseudokódu to vidíte R, C a já se všichni monotónně zvyšují, přičemž každý prochází prvky v S 'a P. (koncová podmínka byla také mírně změněna, aby nevypočítala poslední prvky P -li R je již na konci - ty budou nutně mít délky menší než P [C] a lze je přeskočit).

Použití S 'poskytuje kódu několik zjednodušení: poskytuje řetězec zarovnaný na P umožňuje přímé použití ukazatelů v obou polích a implicitně umožňuje vnitřní smyčce while zdvojnásobit P [i] a R (protože pokaždé bude porovnávat falešný znak sám se sebou).

Poznámky

  1. ^ Crochemore & Rytter (1991), Apostolico, Breslauer & Galil (1995).

Reference

  • Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), "Paralelní detekce všech palindromů v řetězci", Teoretická informatika, 141 (1–2): 163–173, doi:10.1016 / 0304-3975 (94) 00083-U.
  • Crochemore, Maxime; Rytter, Wojciech (1991), „Užitečnost algoritmu Karp – Miller – Rosenberg v paralelních výpočtech na řetězcích a polích“, Teoretická informatika, 88 (1): 59–82, doi:10.1016 / 0304-3975 (91) 90073-B, PAN  1130372.
  • Crochemore, Maxime; Rytter, Wojciech (2003), "8.1 Hledání symetrických slov", Jewels of Stringology: Text Algorithms, World Scientific, str. 111–114, ISBN  978-981-02-4897-0.
  • Gusfield, Dan (1997), „9.2 Nalezení všech maximálních palindromů v lineárním čase“, Algoritmy pro řetězce, stromy a sekvence, Cambridge: Cambridge University Press, s. 197–199, doi:10.1017 / CBO9780511574931, ISBN  0-521-58519-8, PAN  1460730.
  • Jeuring, Johan (1994), „Derivace on-line algoritmů s aplikací pro hledání palindromů“, Algorithmica, 11 (2): 146–184, doi:10.1007 / BF01182773, hdl:1874/20926, PAN  1272521, S2CID  7032332.
  • Manacher, Glenn (1975), "Nový lineární" online "algoritmus pro nalezení nejmenšího počátečního palindromu řetězce", Deník ACM, 22 (3): 346–351, doi:10.1145/321892.321896, S2CID  10615419.

externí odkazy

Tento článek včlení text od Nejdelší palindromický podřetězec na PEGWiki pod Creative Commons Attribution (CC-BY-3.0 ) licence.