Palindrom je slovo které se čte stejně zepředu i pozpátku. Příkladem palindromů jsou řetězce: “madam”, “mam”, “rotor”, “kuna nese nanuk”, “kobyla ma maly bok” (po vynechání mezer).

Úloha: (Nejdelší palindrom) Na vstupu dostanete řětězec $n$ znaků. Navrhněte algoritmus, který v řetězci co nejrychleji nalezne nejdelší palindrom.

Řešení: (jednoduché kvadratické) Každý palindrom má svůj střed kolem kterého je symetrický (levá půlka palindromu je zrcadlovým obrazem pravé půlky). Středy palindromu jsou dvou druhů. Palindromy liché délky mají uprostřed písmeno, palindromy sudé délky mají uprostřed mezeru mezi písmeny.

Řešení, které nás hned napadne, je vyzkoušet všechny možné středy a z každého středu expandovat dosud nalezený palindrom do stran. Takové řešení má v nejhorším případě časovou složitost $\OO(n^2)$. Příkladem řetězce, na kterém algoritmus dosáhneme kvadratické časové složitosti je řetězec se samých a, například aaaaaaaaa.

Řešení: (v lineárlním čase) Jak se dá předchozí algoritmus vylepšit, abychom dosáhli lineální časové složitosti? Základní myšlenka zůstane stejná, chceme pro všechny středy $s$ vyplnit $$ \ARRAY{d}{s} = \mbox{délka nejdelšího palindromu se středem $s$.}$$

Ale jak to udělat? Podívejme se nejprve na malý příklad. Předpokládejme, že už jsme nalezli nejdelší palindrom se středem na pozici $s$. Říkejme mu aktuální master-palindrom. Na obrázku je vyznačen tučně, má délku $7$ znaků a jeho střed je na pozici $6$.

Jaké hodnoty vyplnit do $\ARRAY{d}{7}$, $\ARRAY{d}{8}$,\dots? Kdybychom tyto hodnoty hledali expanzí, tak se vrátíme zpátky ke kvadratické časové složitosti. Využijeme malý trik, kterým je zrcadlení. Protože je pravá půlka palindromu zrcadlovým obrazem levé půlky palindromu, platí $\ARRAY{d}{s+i} = \ARRAY{d}{s-i}$ pokud pravý okraj ozrcadleného palindromu nepřesáhne pravý okraj master-palindromu.

Na obrázku je pravý okraj master-palindromu vyznačen čárou. Ta zároveň odděluje oblast řetězce ze vstupu, která ještě nebyla prozkoumána. V příkladu na obrázku můžeme nastavit $\ARRAY{d}{7}:=1$. Podobně $\ARRAY{d}{8}:=3$, ale to ještě nemusí být délka nejdelšího palindromu se středem na pozici $8$. Tento palindrom délky $3$ se dotýká čáry označující neprozkoumanou oblast a proto možná půjde rozšířit.

Pro všechny středy, jejichž palindromy jsou celé uvnitř aktuálního master-palindromu, můžeme nastavit $\ARRAY{d}{s+i} := \ARRAY{d}{s-i}$. První střed z leva, jehož palindrom se dotýká nebo překračuje hranici master-palindromu, se stane středem $S$ nového master-palindromu.

Nový master-palindrom nalezneme expanzí do stran. Nemusíme začínat úplně od začátku. Už víme, že $\ARRAY{d}{S}$ znaků kolem středu $S$ tvoří palindrom a proto stačí tento palindrom rozšiřovat do stran. První znak řetězce ze vstupu, na který “sáhneme”, bude ten napravo od posledního znaku původního master-palindromu (první znak za čárou).

Algoritmus začne s master-palindromem, jehož střed je na prvním znaku řetězce ze vstupu. Postupně hledá následující master-palindromy a za každý master-palindrom vyplní příslušný úsek pole $\ARRAY{d}{\cdot}$. Na závěr už jen stačí najít maximální hodnotu v tomto poli.

Algoritmus má lineální časovou složitost, protože na každý znak řetězce ze vstupu sáhneme nejvýše dvakrát a protože každé políčko pole $\ARRAY{d}{\cdot}$ vyplňujeme jen jednou.

Poznámka: Nezapomeňte, že palindromy mají dva druhy středů. Jedny leží na pozici písmenka a druhé mezi sousedními písmenky.