Количество подпалиндромов

Палиндром — строка, читающаяся одинаково как слева направо, так и справа налево. Например, строка «abba» является палиндромом. Задача найти все количество подстрок строки которые являются палиндромами.

Алгоритмы поиска количества подпалиндромов в строке

Лобовое решение

Задачу возможно решить «в лоб» для небольших строк, перебирая каждый символ и пытаясь строить от него максимальный палиндром, если этот символ является центром палиндрома (для нечетной длины) или одним из центральных символов (для палиндромов четной длины).также не так

Решение при помощи суффиксных деревьев

Задача решается при помощи суффиксных деревьев и быстрого алгоритма LCA. Сложность такого алгоритма $O(N\log {N})$, где $N$ — длина строки.

Решение с динамическим программированием

Решение при помощи динамического программирования — один из самых быстрых и простых алгоритмов для решения данной задачи.

Заведем массив, размер которого равен длине строки. Назовем массив А, и будем хранить в A[i] количество палиндромов с центром в символе i. Тогда ответом на поставленную задачу будет сумма всех элементов массива.

Разберем нахождение палиндрома нечетной длины от символа в строке с номером i. Будем сравнивать символы, отстоящие слева и справа от i на какое-то число k, и увеличивать k пока они равны и пока выполняются условия i+k <= length(s), i-k >= 1.

Будем хранить границы самого правого уже найденного палиндрома. Пусть L — левый символ этого палиндрома, а R — правый.

Итак, рассматривая очередное i, мы проверяем, является ли оно больше правой границы самого правого из уже найденных палиндромов. Если i > R, то находим палиндром с центром в i по вышеописанному алгоритму. Если i <= R, то найдем элемент, симметричный i относительно центра самого правого палиндрома. Назовем этот элемент j, j = R + L — i. Поиск количества палиндромов для подстроки с центром в i можно начинать с того количества, которое записано в А[j], увеличивая далее это значение по алгоритму, описанному выше. Если правая граница полученного палиндрома больше R, тогда обновляем L и R.

Примеры реализации на языках программирования

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}