299
правок
Изменения
Нет описания правки
== Решение ==
Для решения этой задачи будет необходимо перебрать все подпоследовательности-палиндромы данной последовательности. Наиболее оптимально это можно сделать с помощью алгоритма Манакера.
=== Тривиальный алгоритм ===
Это алгоритм, который для поиска ответа в позиции раз за разом пробует увеличить ответ на единицу, каждый раз сравнивая пару соответствующих символов.
Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время <tex>O(n^2)</tex>
==== Псевдокод ====
Реализация тривиального алгоритма:
List d1(n), d2(n)
for i = 0 to n
d1[i] = 1
while i - d1[i] >= 0 && i + d1[i] < n && s[i-d1[i]] == s[i+d1[i]]
++d1[i]
d2[i] = 0;
while i - d2[i] - 1 >= 0 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]]
++d2[i]
=== Алгоритм Манакера ===
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
if i + k - 1 > r
l = i - k, r = i + k - 1
== См. также ==
