Palindrom jest to wyraz, który jest taki sam niezależnie od której strony go czytamy, np.: kajak.
Niech s = s₁s₂... s_n będzie słowem długości n, (n ≥ 1) nad dowolnym alfabetem. Zadaniem jest obliczyć, dla ilu par liczb całkowitych (i, j), (1 ≤ i ≤ j ≤ n) słowo s_is_i+1... s_j jest palindromem.
Przykład: dla słowa "mama" wynik będzie równy 6 i składać się będą na niego następujące słowa: "m", "a", "m", "a", "mam", "ama". Rozwiązanie tego problemu będzie oparte na ideach programowania dynamicznego.
Niech M będzie dwuwymiarową tablicą logiczną taką, że M_{i, j} = true (1 ≤ i ≤ j ≤ n) jeżeli słowo s_is_i+1... s_j jest palindromem zaś w przeciwnym razie M_{i, j} = false. Jak łatwo zauważyć, jeśli dla pewnych indeksów i, j (1 ≤ i < j ≤ n) słowo s_i+1s_i+2... s_j-1 jest palindromem, to słowo s_is_i+1... s_j jest palindromem wtedy i tylko wtedy, gdy s_i = s_j (domyślnie przyjmujemy, że słowo puste oraz słowo złożone z jednego znaku jest palindromem). Stąd dostajemy:

• M_{i, i} = true, 1 ≤ i ≤ n
• M_{i, j} = (M_{i+1, j–1} AND (s_i = s_j)), 1 ≤ i < j ≤ n

Maksymalna liczbę palindromów, jaką można otrzymać ze słowa długości n wynosi n(n+1)/2 i jest osiągnięta, gdy słowo s składa się z n jednakowych znaków.

Postawmy teraz problem nieco bardziej złożony. Dla danego słowa s = s₁s₂... s_n długości n, (n ≥ 1) nad dowolnym alfabetem zadaniem jest obliczyć, na ile sposobów można wybrać liczby całkowite, k, i₁, i₂, ..., i_k (1 ≤ k ≤ n, 1 ≤ i₁ < i₂ < ... < i_k ≤ n) takie, że słowo s_i1s_i2... s_ik jest palindromem.
Przykład: dla słowa "mama" wynik będzie równy 8 i składać się będą na niego następujące słowa: "m", "a", "m", "a", "mm", "aa", "mam", "ama".
Rozwiązanie tego problemu będzie również oparte na ideach programowania dynamicznego. Niech M będzie dwuwymiarową tablicą taką, że element M_{i, j} (1 ≤ i ≤ j ≤ n) będzie równy ilości sposobów wyboru liczb całkowitych k, i₁, i₂, ..., i_k (1 ≤ k ≤ n, i ≤ i₁ < i₂ < ... < i_k ≤ j ) takich, że słowo s_i1s_i2... _ik jest palindromem. Wówczas rozwiązaniem postawionego problemu będzie wartość M_{1, n}. Oczywiście M_{i, i} = 1, 1 ≤ i ≤ n.
Zastanówmy się teraz, o ile liczba M_{i, j} będzie większa od liczby M_{i+1, j} (1 ≤ i < j ≤ n). Na pewno o przynajmniej 1 gdyż element s_i sam będzie stanowić nowy palindrom. Poza tym, jeżeli dla pewnego k, (i+1 ≤ k ≤ j) zachodzi równość s_i = s_k to różnica M_{i, j} – M_{i+1, j} zwiększy się także o ilość palindromów zawartych w słowie s_i+1s_i+2...s_k-1 powiększoną o jeden. Wprowadzimy funkcję f(i, j), której wartość będzie zdefiniowana następująco:

• 1, jeżeli s_i = s_j
• 0, w przeciwnym razie

Reasumując:

• M_{i, i} = 1, 1 ≤ i ≤ n
• M_{i, j} = M_{i+1, j} + 1 + f(i, i+1)(M_{i+1, i} + 1) + f(i, i+2)(M_{i+1, i+1} + 1)... + f(i, j)(M_{i+1, j-1} + 1), 1 ≤ i < j ≤ n

Maksymalna ilość palindromów, jaką można otrzymać ze słowa długości n wynosi 2ⁿ - 1 i jest osiągnięta, gdy słowo s składa się z n jednakowych znaków.