Количество подпалиндромов: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Leksey (обсуждение | вклад) Откат вандализма |
||
Строка 1:
Палиндром — строка, читающаяся одинаково как слева направо, так и справа налево. Например строка abba является палиндромом.
Задача найти все количество подстрок строки которые являются палиндромами.
== Алгоритмы поиска количества подпалиндромов в строке ==
=== Лобовое решение ===
Задачу возможно решить «в лоб» для небольших строк, перебирая каждый символ и пытаясь строить от него максимальный палиндром, если этот символ является центром палиндрома (для нечетной длины) или одним из центральных символов (для палиндромов четной длины).
=== Решение при помощи суффиксных деревьев ===
Задача решается при помощи суффиксных деревьев и быстрого алгоритма LCA. Сложность такого алгоритма <math>O(N \log{N})</math>, где <math>N</math> — длина строки.
=== Решение с динамическим программированием ===
[[Категория:Дыхание]]▼
Решение при помощи динамического программирования — один из самых быстрых и простых алгоритмов для решения данной задачи.
Заведем массив, размер которого равен длине строки. Назовем массив <code>А</code>, и будем хранить в <code>A[i]</code> количество палиндромов с центром в символе <code>i</code>. Тогда ответом на поставленную задачу будет сумма всех элементов массива.
Разберем нахождение палиндрома нечетной длины от символа в строке с номером <code>i</code>. Будем сравнивать символы, отстоящие слева и справа от <code>i</code> на какое-то число <code>k</code>, и увеличивать <code>k</code> пока они равны и пока выполняются условия <code>i+k <= length(s)</code>, <code>i-k >= 1</code>.
Будем хранить границы самого правого уже найденного палиндрома. Пусть <code>L</code> — левый символ этого палиндрома, а <code>R</code> — правый.
Итак, рассматривая очередное <code>i</code>, мы проверяем, является ли оно больше правой границы самого правого из уже найденных палиндромов. Если <code>i > R</code>, то находим палиндром с центром в <code>i</code> по вышеописанному алгоритму. Если <code>i <= R</code>, то найдем элемент, симметричный <code>i</code> относительно центра самого правого палиндрома. Назовем этот элемент <code>j</code>, <code>j = R + L — i</code>. Поиск количества палиндромов для подстроки с центром в <code>i</code> можно начинать с того количества, которое записано в <code>А[j]</code>, увеличивая далее это значение по алгоритму, описанному выше. Если правая граница полученного палиндрома больше <code>R</code>, тогда обновляем <code>L</code> и <code>R.</code>
== Примеры реализации на языках программирования ==
=== Pascal ===
<source lang="pascal">
r := -1; {обнуляем начальные значения l и r}
{в конце и начале строки добавляем по символу, который в строке встречаться не может}
for i:=2 to n do begin
if i>r then
x:=1
else x:=min(a[l+r-i],r-i)+1;
while (i+x<=n)and(stroka[i-x]=stroka[i+x])and(i-x>=2) do {наращиваем x пока палиндром}
inc(x);
a[i]:=x-1;
if i+x-1>r then
begin R:=i+x-1;L:=i-x+1; end;
end;{так мы нашли количество палиндромов нечетной длины}
{четной длины находятся аналогично. все вхождения х заменить на х - 1}
</source>
|