Палиндромная характеристика строки s длины |s| — это последовательность из |s| целых чисел, k-е из которых равно количеству непустых подстрок строки s, являющихся k-палиндромами.

Строка является 1-палиндромом тогда и только тогда, когда она читается одинаково как слева-направо, так и справа-налево.

Строка является k-палиндромом (k > 1) тогда и только тогда, когда:

1. Её левая половина равна правой половине.
2. Её левая и правая половины не пусты и являются (k - 1)-палиндромами.

Левая половина строки t — это её префикс длины ⌊|t| / 2⌋, а правая — её суффикс той же длины. ⌊|t| / 2⌋ обозначает длину строки t, делённую на 2, округленную вниз.

Обратите внимание, что каждая подстрока учитывается столько раз, сколько встречается как подстрока. Так, например, в строке «aaa» подстрока «a» встречается 3 раза.