Acum daca vrem sa calculam $LUNG{~9~}$ ar trebui sa ne extindem cat putem in lateral fata de {$b$}, dar observam ca centrul palindromului curent este continut in palindromul centrat la {$6$}. Din faptul ca palindromul contine doua subsecvente oglindite, noi nu trebuie sa mai iteram prin literele palindromului nostru pentru ca avem deja rezolvata problema oglindita, si continuam comparatiile cu caractere noi (in cazul nostru avem deja rezolvata problema {$a b a$} in secventa [{$1..5$}] si nu mai trebuie sa o rezolvam inca o data). Am obtinut astfel o rezolvare simpla de complexitate {$O(N)$}. Mentionam ca sursa oficiala nu are mai mult de $50$ de linii.

Exista si alte rezolvari optime posibile si ii rugam pe cei care au luat $100$ de puncte sa le explice in cadrul "forumului":http://forum.infoarena.ro/index.php/board,25.0.html.

Exista si alte rezolvari optime posibile si ii rugam pe cei care au luat $100$ de puncte sa le explice in cadrul forumului.