Палиндромная характеристика строки s длины |s| — это последовательность из |s| целых чисел, k-е из которых равно количеству непустых подстрок строки s, являющихся k-палиндромами.
Строка является 1-палиндромом тогда и только тогда, когда она читается одинаково как слева-направо, так и справа-налево.
Строка является k-палиндромом (k > 1) тогда и только тогда, когда:
- Её левая половина равна правой половине.
- Её левая и правая половины не пусты и являются (k - 1)-палиндромами.
Левая половина строки t — это её префикс длины ⌊|t| / 2⌋, а правая — её суффикс той же длины. ⌊|t| / 2⌋ обозначает длину строки t, делённую на 2, округленную вниз.
Обратите внимание, что каждая подстрока учитывается столько раз, сколько встречается как подстрока. Так, например, в строке «aaa» подстрока «a» встречается 3 раза.
Примечание
В первом примере 1-палиндромами являются подстроки «a», «b», «b», «a», «bb», «abba», 2-палиндромом является подстрока «bb». 3- и 4-палиндромы у этой строки отсутствуют.