299
правок
Изменения
Нет описания правки
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
== Решение (алгоритм ===== Алгоритм Манакера) ===
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов <tex>d_1[]</tex>; для массива чётных палиндромов <tex>d_2[]</tex> все рассуждения аналогичны.
==== Оценка асимптотики ====
==== Псевдокод ====
=== Тривиальный алгоритм ===
==== Псевдокод ====
== См. также ==
*[[wikipedia:Palindrome|Wikipedia — Palindrome]]
*[[wikipedia:ru:Палиндром|Википедия — Палиндром]]
*[http://e-maxx.ru/algo/palindromes_count Нахождение всех подпалиномов]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
