Na początku wprowadźmy kilka oznaczeń. Jeśli  jest słowem, to przez  oznaczymy  czytane od tyłu. Zatem  jest palindromem, jeśli  Dalej, przez  oznaczymy prefiks  o długości (a więc pierwsze  liter słowa ), za to przez – sufiks  o długości (tj.  ostatnich liter ). I jeszcze, niech  będzie długością słowa

Zacznijmy od kilku spostrzeżeń, które narzucają się po przeanalizowaniu choćby przykładu do tego zadania – Czytelnikowi proponuję rozpisanie własnego i przyjrzenie mu się. Po pierwsze, na pewno każdy palindrom  z wejścia zwiększa wynik co najmniej o   Jest tak dlatego, że skoro  to  Po drugie, niech  i   będą takimi palindromami, że  też jest palindromem, oraz niech (zachodzi albo to, albo nierówność w drugą stronę – długości nie mogą być sobie równe, bo wtedy mielibyśmy ). Wtedy  również jest palindromem. Faktycznie, zachodzi  a ponadto  jest palindromem, więc  również. Łatwo zauważyć, że występuje tutaj równoważność, czyli jeśli  jest palindromem, to  również.

Sumarycznym wynikiem jest więc  gdzie  to liczba takich par różnych palindromów  że

No to teraz możemy zastanowić się nad tym, kiedy dwa palindromy  i   tworzą palindrom  Na pewno trzeba, żeby  czyli żeby  było prefiksem  Poza tym jeszcze  musi być palindromem (jest to środek  po ucięciu z początku i z końca  liter). Na bazie tych dwóch warunków zbudujemy już rozwiązanie zadania.

Zacznijmy od tego, jak znaleźć wszystkie palindromy  z wejścia, będące prefiksami palindromu  Załóżmy, że wejście jest posortowane leksykograficznie. Zauważmy, że jeśli  jest prefiksem  to w kolejności leksykograficznej między nimi mogą znaleźć się tylko takie słowa  że  jest prefiksem  Załóżmy, że mamy policzoną listę  wszystkich spośród naszych palindromów, które są prefiksami  występuje bezpośrednio przed  w kolejności leksykograficznej oraz znamy maksymalne możliwe  spełniające (obliczenie takiego  to koszt ). Wtedy lista wszystkich spośród naszych słów, które są prefiksami  to lista  uzupełniona o   z której zostały usunięte wszystkie słowa dłuższe niż  Długość tej listy dla  jest ograniczona przez długość (na wejściu mamy parami różne palindromy), a więc cała operacja otrzymania listy dla  z listy dla  ma koszt

W drugim kroku chcielibyśmy sprawdzić, dla danej pary palindromów  i   gdzie  występuje na liście odpowiadającej  czy rzeczywiście  jest palindromem, czyli czy  też nim jest.  jest palindromem wtedy i tylko wtedy, gdy

A w takim razie  musi być jednocześnie i prefiksem, i sufiksem słowa  A to już brzmi znajomo – w tym momencie warto skorzystać z algorytmu Knutha–Morrisa–Pratta (Czytelnikowi nieobeznanemu z tym algorytmem polecam skorzystanie z mnóstwa materiałów dostępnych w Internecie). W tym algorytmie wyznaczana jest tablica prefiksowa  w której  jest długością najdłuższego prefiksu, będącego jednocześnie sufiksem słowa  Zauważmy, że długością najdłuższego prefiksu, będącego jednocześnie sufiksem  jest  następnego najdłuższego –  itd., aż w końcu  Algorytm KMP oblicza tablicę  w czasie  a my w takim samym czasie możemy odczytać z niej długości wszystkich prefiksów  będących sufiksami  czyli palindromami. Po tych wstępnych obliczeniach można już natychmiastowo sprawdzić, dla każdego palindromu  z listy odpowiadającej  czy  jest palindromem.

W takim razie sumaryczny czas, jaki musimy poświęcić  jest rzędu  gdzie  jest poprzednim leksykograficznie palindromem, a więc sumaryczny czas całego algorytmu, nie licząc sortowania, to  Czytelnikowi pozostawiam sprytną implementację algorytmu sortowania pozycyjnego tak, żeby złożoność całego algorytmu pozostała  Liczba „obrotów” sortowania może być bliska  ze względu na rozmiar alfabetu – chociaż tę stałą da się znacząco zmniejszyć, co również polecam jako ćwiczenie.