E105. Нахождение всех подпалиндромов

Источник: e-maxx.ru/algo, страница PDF 329.

Постановка задачи

Дана 문자열

длины

. it is required find все такие пары

, где

, что substring

является палиндромом (т.е. читается одинаково слева направо и справа налево).

Уточнение постановки

Понятно, что в худшем случае таких подстрок-палиндромов может быть

, и на первый взгляд кажется,

что 알고리즘а с линейной асимптотикой существовать не может. Однако информацию о найденных палиндромах можно возвращать более компактно: для каждой

позиции

найдём значения

и

, обозначающие количество палиндромов

соответственно нечётной и чётной длины с центром в позиции

.

На예제, в строке

есть три палиндрома нечётной длины с центром в символе

, т.е.

значение

:

А в строке

есть два палиндрома чётной длины с центром в символе

, т.е. значение

:

Т.е. идея — в том, что если есть подпалиндром длины

с центром в какой-то позиции

, то есть также

подпалиндромы длины

,

, и т.д. с центрами в

. Поэтому двух таких 배열ов

и

достаточно

для хранения информации обо всех подпалиндромах этой строки. Достаточно неожиданным фактом является то, что существует довольно простой 알고리즘, который вычисляет

эти "배열ы палиндромностей"

и

за линейное время. Этот 알고리즘 и описывается в данной статье.

해법

Вообще говоря, данная 문제 имеет несколько известных решений: с помощью техники хэширования её можно решить

за

, а с помощью суффиксных деревьев и быстрого 알고리즘а LCA эту задачу можно решить за . Однако описываемый в данной статье метод значительно проще, и обладает меньшими скрытыми константами в асимптотике времени и памяти. Этот 알고리즘 был открыт Гленном Манакером (Glenn Manacher) в 1975 г.

Тривиальный 알고리즘

Во избежание неоднозначностей при дальнейшем описании условимся, что же такое есть "тривиальный 알고리즘".

Это 알고리즘, который для поиска ответа в позиции

раз за разом пробует увеличить ответ на единицу, каждый

раз сравнивая пару соответствующих символов. Такой 알고리즘 слишком медленен, весь ответ он может посчитать лишь за время . Приведём для наглядности его реализацию:

vector<int> d1 (n), d2 (n);

for (int i=0; i<n; ++i) {

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];

}

알고리즘 Манакера

Научимся сначала находить все подпалиндромы нечётной длины, т.е. вычислять 배열

; 해법 для

палиндромов чётной длины (т.е. нахождение 배열а

) получится небольшой модификацией этого.

Для быстрого вычисления будем поддерживать границы

самого правого из обнаруженных подпалиндрома (т.

е. подпалиндрома с наибольшим значением

). Изначально можно положить

.

Итак, пусть мы хотим вычислить значение

для очередного

, при этом все предыдущие значения

уже подсчитаны.

● Если

не находится в пределах текущего подпалиндрома, т.е. , то просто выполним тривиальный 알고리즘.

Т.е. будем последовательно увеличивать значение

, и проверять каждый раз — правда ли текущая

substring

является палиндромом. Когда мы найдём первое расхождение, либо когда мы

дойдём до границ строки

— останавливаемся: мы окончательно посчитали значение

. После этого мы должны

не забыть обновить значения

.

● Рассмотрим теперь случай, когда

.

Попробуем извлечь часть информации из уже подсчитанных значений

. А именно, отразим позицию

внутри подпалиндрома

, т.е. получим позицию

, и рассмотрим значение

. Поскольку

— позиция, симметричная позиции

, то почти всегда мы можем просто присвоить

.

Иллюстрация этого отражения (палиндром вокруг

фактически "копируется" в палиндром вокруг

): Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е.

(или, что то же самое,

). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то

просто присвоить

будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в

позиции

подпалиндром имеет такую же длину. На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину подпалиндрома, т.е.

присвоить

. После этого следует пустить тривиальный 알고리즘, который будет пытаться

увеличить значение

, пока это возможно.

Иллюстрация этого случая (на ней палиндром с центром в

изображён уже "обрезанным" до такой длины, что он

впритык помещается во внешний палиндром): (На этой иллюстрации показано, что, хотя палиндром с центром в позиции

мог быть и более длинным, 출력ящим

за пределы внешнего палиндрома, — но в позиции

мы можем использовать только ту его часть, которая

целиком помещается во внешний палиндром. Но ответ для позиции

может быть больше, чем эта часть, поэтому

дальше мы должны запустить тривиальный поиск, который будет пытаться раздвинуть его за пределы

внешнего палиндрома, т.е. в область "try moving here".)

В завершение описания 알고리즘а сталось только напомнить, что надо не забывать обновлять значения

после вычисления очередного значения

. Также повторимся, что выше мы описали рассуждения для вычисления 배열а нечётных палиндромов

; для

배열а чётных палиндромов

все рассуждения аналогичны.

Оценка асимптотики 알고리즘а Манакера

На первый взгляд не очевидно, что данный 알고리즘 имеет линейную асимптотику: при вычислении ответа для определённой позиции в нём нередко запускается тривиальный 알고리즘 поиска палиндромов. Однако более внимательный анализ показывает, что 알고리즘 всё же линеен. (Стоит сослаться на известный 알고리즘 построения Z-функции строки, который внутренне сильно напоминает данный 알고리즘, и работает также

за линейное время.)

В самом деле, легко проследить по 알고리즘у, что каждая итерация, производимая тривиальным поиском, приводит

к увеличению на один границы

. При этом уменьшений

по ходу 알고리즘а происходить не может.

Следовательно, тривиальный 알고리즘 в сумме совершит лишь

действий. given, что, кроме тривиальных поисков, все остальные части 알고리즘а Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику: .

구현 알고리즘а Манакера

Для случая подпалиндромов нечётной длины, т.е. для вычисления 배열а , получаем такой код:

vector<int> d1 (n);

int l=0, r=-1;

for (int i=0; i<n; ++i) {

int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;

while (i+k < n && i-k >= 0 && s[i+k] == s[i-k])  ++k;

d1[i] = k--;

if (i+k > r)

l = i-k, r = i+k;

}

Для подпалиндромов чётной длины, т.е. для вычисления 배열а

, лишь немного меняются

арифметические выражения:

vector<int> d2 (n);

l=0, r=-1;

for (int i=0; i<n; ++i) {

int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;

while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k])  ++k;

d2[i] = --k;

if (i+k-1 > r)

l = i-k, r = i+k-1;

}

Задачи в online judges

Список задач, которые можно сдать с использованием этого 알고리즘а:

● UVA #11475 "Extend to Palindrome" [Complexity: низкая]

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    List<int> d1 (n),  d2 (n);
    for (int i=0; i<n; ++i) {
            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];
    }
    List<int> d1 (n);
    int l=0, r=-1;
    for (int i=0; i<n; ++i) {
            int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;
            while (i+k < n && i-k >= 0 && s[i+k] == s[i-k])  ++k;
            d1[i] = k--;
            if (i+k > r)
                    l = i-k,  r = i+k;
    }
    List<int> d2 (n);
    l=0, r=-1;
    for (int i=0; i<n; ++i) {
            int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;
            while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k])  ++k;
            d2[i] = --k;
            if (i+k-1 > r)
                    l = i-k,  r = i+k-1;
    }
}

vector<int> d1 (n),  d2 (n);
for (int i=0; i<n; ++i) {
        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];
}
vector<int> d1 (n);
int l=0, r=-1;
for (int i=0; i<n; ++i) {
        int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;
        while (i+k < n && i-k >= 0 && s[i+k] == s[i-k])  ++k;
        d1[i] = k--;
        if (i+k > r)
                l = i-k,  r = i+k;
}
vector<int> d2 (n);
l=0, r=-1;
for (int i=0; i<n; ++i) {
        int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;
        while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k])  ++k;
        d2[i] = --k;
        if (i+k-1 > r)
                l = i-k,  r = i+k-1;
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    ArrayList<Integer> d1 (n),  d2 (n);
    for (int i=0; i<n; ++i) {
            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];
    }
    ArrayList<Integer> d1 (n);
    int l=0, r=-1;
    for (int i=0; i<n; ++i) {
            int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;
            while (i+k < n && i-k >= 0 && s[i+k] == s[i-k])  ++k;
            d1[i] = k--;
            if (i+k > r)
                    l = i-k,  r = i+k;
    }
    ArrayList<Integer> d2 (n);
    l=0, r=-1;
    for (int i=0; i<n; ++i) {
            int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;
            while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k])  ++k;
            d2[i] = --k;
            if (i+k-1 > r)
                    l = i-k,  r = i+k-1;
    }
}