E099. Префикс-функция. Algorithmus Кнута- Морриса-Пратта

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

Префикс-функция. Definition

Дана Zeichenkette

. it is required вычислить для неё префикс-функцию, т.е. Array чисел

,

где

определяется следующим образом: это такая наибольшая длина наибольшего собственного суффикса

подстроки

, совпадающего с её префиксом (собственный суффикс — значит не совпадающий со всей

строкой). В частности, значение

полагается равным нулю. Математически Definition префикс-функции можно записать следующим образом: НаBeispiel, для строки "abcabcd" префикс-функция равна: , что означает:

● у строки "a" нет нетривиального префикса, совпадающего с суффиксом;

● у строки "ab" нет нетривиального префикса, совпадающего с суффиксом;

● у строки "abc" нет нетривиального префикса, совпадающего с суффиксом;

● у строки "abca" префикс длины

совпадает с суффиксом;

● у строки "abcab" префикс длины

совпадает с суффиксом;

● у строки "abcabc" префикс длины

совпадает с суффиксом;

● у строки "abcabcd" нет нетривиального префикса, совпадающего с суффиксом.

Другой Beispiel — для строки "aabaaab" она равна: .

Тривиальный Algorithmus

Непосредственно следуя определению, можно написать такой Algorithmus вычисления префикс-функции:

vector<int> prefix_function (string s) {

int n = (int) s.length();

vector<int> pi (n);

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

for (int k=0; k<=i; ++k)

if (s.substr(0,k) == s.substr(i-k+1,k))

pi[i] = k;

return pi;

}

Как нетрудно заметить, работать он будет за

, что слишком медленно.

Эффективный Algorithmus

Этот Algorithmus был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г. (как основной element для Algorithmusа поиска подстроки в строке).

Первая оптимизация

Первое важное замечание — что значение

не более чем на единицу превосходит значение

для любого

.

Действительно, в противном случае, если бы

, то рассмотрим этот суффикс, оканчивающийся

в позиции

и имеющий длину

— удалив из него последний символ, мы получим

суффикс, оканчивающийся в позиции

и имеющий длину

, что лучше

, т.е. пришли к

противоречию. Иллюстрация этого противоречия (в этом Beispielе

должно быть равно 3): (на этой схеме верхние фигурные скобки обозначают две одинаковые подстроки длины 2, нижние фигурные скобки —

две одинаковые подстроки длины 4)

Таким образом, при переходе к следующей позиции очередной element префикс-функции мог либо увеличиться на единицу, либо не измениться, либо уменьшиться на какую-либо величину. Уже этот факт позволяет нам

снизить асимптотику до

— поскольку за один шаг значение могло вырасти максимум на единицу, то суммарно

для всей строки могло произойти максимум

увеличений на единицу, и, как следствие (т.к. значение никогда не

могло стать меньше нуля), максимум

уменьшений. В итоге получится

сравнений строк, т.е. мы уже

достигли асимптотики

.

Вторая оптимизация

Пойдём дальше — избавимся от явных сравнений подстрок. Для этого постараемся максимально использовать информацию, вычисленную на предыдущих шагах.

Итак, пусть мы вычислили значение префикс-функции

для некоторого

. Теперь, если

, то

мы можем с уверенностью сказать, что

, это иллюстрирует схема: (на этой схеме снова одинаковые фигурные скобки обозначают одинаковые подстроки)

Пусть теперь, наоборот, оказалось, что

. Тогда нам надо попытаться попробовать

подстроку меньшей длины. В целях оптимизации хотелось бы сразу перейти к такой (наибольшей) длине

,

что по-прежнему выполняется префикс-свойство в позиции

, т.е. :

Действительно, когда мы найдём такую длину

, то нам будет снова достаточно сравнить символы

и

— если они совпадут, то можно утверждать, что

. Иначе нам надо будет снова find

меньшее (следующее по величине) значение

, для которого выполняется префикс-свойство, и так далее.

Может случиться, что такие значения

кончатся — это происходит, когда

. В этом случае,

если

, то

, иначе

. Итак, общая схема Algorithmusа у нас уже есть, нерешённым остался только вопрос об эффективном нахождении таких

длин

. Поставим этот вопрос формально: по текущей длине

и позиции

(для которых выполняется префикс-свойство,

т.е.

) it is required find наибольшее

, для которого по-

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

есть не что иное, как

значение префикс-функции

, которое уже было вычислено нами ранее (вычитание единицы появляется из-за

0-индексации строк). Таким образом, находить эти длины

мы можем за

каждую.

Итоговый Algorithmus

Итак, мы окончательно построили Algorithmus, который не содержит явных сравнений строк и выполняет действий. Приведём здесь итоговую схему Algorithmusа:

● Считать значения префикс-функции

будем по очереди: от

к

(значение

просто

присвоим равным нулю).

● Для подсчёта текущего значения

мы заводим переменную

, обозначающую длину текущего

рассматриваемого образца. Изначально

.

● Тестируем образец длины

, для чего сравниваем символы

и

. Если они совпадают — то

полагаем

и переходим к следующему индексу

. Если же символы отличаются, то уменьшаем

длину

, полагая её равной

, и повторяем этот шаг Algorithmusа с начала.

● Если мы дошли до длины

и так и не нашли совпадения, то останавливаем процесс перебора образцов и

полагаем

и переходим к следующему индексу

.

Implementierung

Algorithmus в итоге получился удивительно простым и лаконичным:

vector<int> prefix_function (string s) {

int n = (int) s.length();

vector<int> pi (n);

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

int j = pi[i-1];

while (j > 0 && s[i] != s[j])

j = pi[j-1];

if (s[i] == s[j])  ++j;

pi[i] = j;

}

return pi;

} Как нетрудно заметить, этот Algorithmus является онлайновым Algorithmusом, т.е. он обрабатывает данные по ходу поступления — можно, наBeispiel, считывать строку по одному символу и сразу обрабатывать этот символ, находя ответ для очередной позиции. Algorithmus требует хранения самой строки и предыдущих вычисленных значений префикс-функции, однако, как нетрудно заметить, если нам заранее известно максимальное значение, которое может принимать префикс-функция на всей строке, то достаточно будет хранить лишь на единицу большее количество первых символов строки и значений префикс-функции.

Applications

Поиск подстроки в строке. Algorithmus Кнута-Морриса-Пратта

Эта Aufgabe является классическим применением префикс-функции (и, собственно, она и была открыта в связи с этим).

Дан текст

и Zeichenkette

, it is required find и вывести позиции всех вхождений строки

в текст

.

Обозначим для удобства через

длину строки

, а через

— длину текста

.

Образуем строку

, где символ

— это разделитель, который не должен нигде более

встречаться. Посчитаем для этой строки префикс-функцию. Теперь рассмотрим её значения, кроме первых

(которые, как видно, относятся к строке

и разделителю). По определению, значение

показывает наидлиннейшую длину подстроки, оканчивающейся в позиции

и совпадающего с префиксом. Но в

нашем случае это

— фактически длина наибольшего блока совпадения со строкой

и оканчивающегося в позиции

. Больше, чем

, эта длина быть не может — за счёт разделителя. А вот равенство

(там, где

оно достигается), означает, что в позиции

оканчивается искомое вхождение строки

(только не надо забывать, что

все позиции отсчитываются в склеенной строке

).

Таким образом, если в какой-то позиции

оказалось

, то в позиции

строки

начинается очередное вхождение строки

в строку

. Как уже упоминалось при описании Algorithmusа вычисления префикс-функции, если известно, что значения префикс-функции не будут превышать некоторой величины, то достаточно хранить не всю строку и префикс-функцию, а только её начало. В нашем случае это означает, что нужно хранить в памяти лишь строку

и значение

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

и пересчитывать текущее значение

префикс-функции.

Итак, Algorithmus Кнута-Морриса-Пратта решает эту задачу за

времени и

памяти.

Подсчёт числа вхождений каждого префикса

Здесь мы рассмотрим сразу две задачи. Дана Zeichenkette

длины

. В первом варианте it is required для каждого

префикса

посчитать, сколько раз он встречается в самой же строке

. Во втором варианте задачи дана

другая Zeichenkette

, и it is required для каждого префикса

посчитать, сколько раз он встречается в

.

Решим сначала первую задачу. Рассмотрим в какой-либо позиции

значение префикс-функции в ней

.

По определению, оно означает, что в позиции

оканчивается вхождение префикса строки

длины

, и

никакой больший префикс оканчиваться в позиции

не может. В то же время, в позиции

могло оканчиваться и

вхождение префиксов меньших длин (и, очевидно, совсем не обязательно длины

). Однако, как

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

вычисления префикс-функции: по данной длине

надо сказать, какой наидлиннейший её собственный суффикс

совпадает с её префиксом. Мы уже выяснили, что ответом на этот вопрос будет

. Но тогда и в этой задаче,

если в позиции

оканчивается вхождение подстроки длины

, совпадающей с префиксом, то в

также

оканчивается вхождение подстроки длины

, совпадающей с префиксом, а для неё применимы те

же рассуждения, поэтому в

также оканчивается и вхождение длины

и так далее (пока индекс

не станет нулевым). Таким образом, для вычисления ответа мы должны выполнить такой цикл:

vector<int> ans (n+1);

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

++ans[pi[i]];

for (int i=n-1; i>0; --i)

ans[pi[i-1]] += ans[i];

Здесь мы для каждого значения префикс-функции сначала посчитали, сколько раз он встречался в Arrayе

, а

затем посчитали такую в некотором роде динамику: если мы знаем, что префикс длины

встречался ровно

раз,

то именно такое количество надо прибавить к числу вхождений его длиннейшего собственного суффикса, совпадающего с его префиксом; затем уже из этого суффикса (конечно, меньшей чем

длины) выполнится "пробрасывание"

этого количества к своему суффиксу, и т.д. Теперь рассмотрим вторую задачу. Применим стандартный приём: припишем к строке

строку

через разделитель, т.

е. получим строку

, и посчитаем для неё префикс-функцию. Единственное отличие от первой задачи будет в том, что учитывать надо только те значения префикс-функции, которые относятся к строке

, т.е. все

для

.

Количество различных подстрок в строке

Дана Zeichenkette

длины

. it is required посчитать количество её различных подстрок. Будем решать эту задачу итеративно. А именно, научимся, зная текущее количество различных подстрок, пересчитывать это количество при добавлении в конец одного символа.

Итак, пусть

— текущее количество различных подстрок строки

, и мы добавляем в конец символ

. Очевидно,

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

. А

именно, добавляются в качестве новых те подстроки, оканчивающиеся на символе и не встречавшиеся ранее.

Возьмём строку

и инвертируем её (запишем символы в обратном порядке). Наша Aufgabe —

посчитать, сколько у строки

таких префиксов, которые не встречаются в ней более нигде. Но если мы посчитаем

для строки

префикс-функцию и найдём её максимальное значение

, то, очевидно, в строке

встречается (не

в начале) её префикс длины

, но не большей длины. Понятно, префиксы меньшей длины уж точно встречаются в ней. Итак, мы получили, что number новых подстрок, появляющихся при дописывании символа

,

равно

.

Таким образом, для каждого дописываемого символа мы за

можем пересчитать количество различных

подстрок строки. Следовательно, за

мы можем find количество различных подстрок для любой заданной строки. Стоит заметить, что совершенно аналогично можно пересчитывать количество различных подстрок и при дописывании символа в начало, а также при удалении символа с конца или с начала.

Сжатие строки

Дана Zeichenkette

длины

. it is required find самое короткое её "сжатое" представление, т.е. find такую строку

наименьшей длины, что

можно представить в виде конкатенации одной или нескольких копий . Понятно, что проблема является в нахождении длины искомой строки

. Зная длину, ответом на задачу будет,

наBeispiel, префикс строки

этой длины.

Посчитаем по строке

префикс-функцию. Рассмотрим её последнее значение, т.е.

, и введём

обозначение

. Покажем, что если

делится на

, то это

и будет длиной ответа,

иначе эффективного сжатия не существует, и ответ равен

.

Действительно, пусть

делится на

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

, причём,

по определению префикс-функции, префикс длины

будет совпадать с её суффиксом. Но тогда последний

блок должен будет совпадать с предпоследним, предпоследний - с предпредпоследним, и т.д. В итоге получится, что

все блоки блоки совпадают, и такое

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

, то и

префикс-функция на конце была бы больше, чем

, т.е. пришли к противоречию.

Пусть теперь

не делится на

. Покажем, что отсюда следует, что длина ответа равна

. Докажем от противного

— предположим, что ответ существует, и имеет длину

(

делитель

). Заметим, что префикс-функция

необходимо должна быть больше

, т.е. этот суффикс должен частично накрывать первый блок. Теперь рассмотрим второй блок строки; т.к. префикс совпадает с суффиксом, и и префикс, и суффикс покрывают этот блок, и

их смещение друг относительно друга

не делит длину блока

(а иначе бы

делило

), то все символы

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

Построение автомата по префикс-функции

Вернёмся к уже неоднократно использованному приёму конкатенации двух строк через разделитель, т.е. для данных

строк

и

вычисление префикс-функции для строки

. Очевидно, что т.к. символ

является

разделителем, то значение префикс-функции никогда не превысит

. Отсюда следует, что, как

упоминалось при описании Algorithmusа вычисления префикс-функции, достаточно хранить только строку

и значения префикс-функции для неё, а для всех последующих символов префикс-функцию вычислять на лету:

Действительно, в такой ситуации, зная очередной символ

и значение префикс-функции в предыдущей

позиции, можно будет вычислить новое значение префикс-функции, никак при этом не используя все

предыдущие символы строки

и значения префикс-функции в них. Другими словами, мы можем построить автомат: состоянием в нём будет текущее значение префикс- функции, переходы из одного состояния в другое будут осуществляться под действием символа:

Таким образом, даже ещё не имея строки

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

переходов

с помощью того же Algorithmusа вычисления префикс-функции:

string s; // Eingabeная Zeichenkette

const int alphabet = 256; // мощность алфавита символов, обычно меньше

s += '#';

int n = (int) s.length();

vector<int> pi = prefix_function (s);

vector < vector<int> > aut (n, vector<int> (alphabet));

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

for (char c=0; c<alphabet; ++c) {

int j = i;

while (j > 0 && c != s[j])

j = pi[j-1];

if (c == s[j])  ++j;

aut[i][c] = j;

}

Правда, в таком виде Algorithmus будет работать за

(

— мощность алфавита). Но заметим, что

вместо внутреннего цикла

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

вычисленной частью таблицы: переходя от значения

к значению

, мы фактически говорим, что переход

из состояния

приведёт в то же состояние, что и переход

, а для него ответ уже точно посчитан (т. к. ):

string s; // Eingabeная Zeichenkette

const int alphabet = 256; // мощность алфавита символов, обычно меньше

s += '#';

int n = (int) s.length();

vector<int> pi = prefix_function (s);

vector < vector<int> > aut (n, vector<int> (alphabet));

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

for (char c=0; c<alphabet; ++c)

if (i > 0 && c != s[i])

aut[i][c] = aut[pi[i-1]][c];

else

aut[i][c] = i + (c == s[i]);

В итоге получилась крайне простая Implementierung построения автомата, работающая за . Когда может быть полезен такой автомат? Для начала вспомним, что мы считаем префикс-функцию для

строки

, и её значения обычно используют с единственной целью: find все вхождения строки

в строку

. Поэтому самая очевидная польза от построения такого автомата — ускорение вычисления

префикс-функции для строки

. Построив по строке

автомат, нам уже больше не нужна

ни Zeichenkette

, ни значения префикс-функции в ней, не нужны и никакие вычисления — все переходы (т.е. то, как будет меняться префикс-функция) уже предпосчитаны в таблице. Но есть и второе, менее очевидное применение. Это случай, когда Zeichenkette

является гигантской

строкой, построенной по какому-либо правилу. Это может быть, наBeispiel, Zeichenkette Грея или Zeichenkette, образованная рекурсивной комбинацией нескольких коротких строк, поданных на Eingabe.

Пусть для определённости мы решаем такую задачу: дан номер

строки Грея, и дана Zeichenkette

длины

. it is required посчитать количество вхождений строки

в

-ю строку Грея. Напомним, строки

Грея определяются таким образом:

В таких случаях даже просто построение строки

будет невозможным из-за её астрономической длины (наBeispiel,

-

ая Zeichenkette Грея имеет длину

). Тем не менее, мы сможем посчитать значение префикс-функции на конце этой строки, зная значение префикс-функции, которое было перед началом этой строки. Итак, помимо самого автомата также посчитаем такие величины:

— значение автомата, достигаемое

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

, если до этого автомат находился в состоянии

. Вторая величина —

— количество вхождений строки

в строку

, если до "скармливания" этой строки

автомат находился в состоянии

. Фактически,

— это количество раз, которое автомат принимал значение

за

время "скармливания" строки

. Понятно, что ответом на задачу будет величина

. Как считать эти величины? Во-первых, базовыми значениями являются

,

. А

все последующие значения можно вычислять по предыдущим значениям и используя автомат. Итак, для вычисления

этих значений для некоторо

...

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> prefix_function (string s) {
            int n = (int) s.length();
            List<int> pi (n);
            for (int i=0; i<n; ++i)
                    for (int k=0; k<=i; ++k)
                            if (s.substr(0,k) == s.substr(i-k+1,k))
                                    pi[i] = k;
            return pi;
    }
    List<int> prefix_function (string s) {
            int n = (int) s.length();
            List<int> pi (n);
            for (int i=1; i<n; ++i) {
                    int j = pi[i-1];
                    while (j > 0 && s[i] != s[j])
                            j = pi[j-1];
                    if (s[i] == s[j])  ++j;
                    pi[i] = j;
            }
            return pi;
    }
    List<int> ans (n+1);
    for (int i=0; i<n; ++i)
            ++ans[pi[i]];
    for (int i=n-1; i>0; --i)
            ans[pi[i-1]] += ans[i];
    string s; // входная строка
    const int alphabet = 256; // мощность алфавита символов, обычно меньше
    s += '#';
    int n = (int) s.length();
    List<int> pi = prefix_function (s);
    vector < List<int> > aut (n, List<int> (alphabet));
    for (int i=0; i<n; ++i)
            for (char c=0; c<alphabet; ++c) {
                    int j = i;
                    while (j > 0 && c != s[j])
                            j = pi[j-1];
                    if (c == s[j])  ++j;
                    aut[i][c] = j;
            }
    string s; // входная строка
    const int alphabet = 256; // мощность алфавита символов, обычно меньше
    s += '#';
    int n = (int) s.length();
    List<int> pi = prefix_function (s);
    vector < List<int> > aut (n, List<int> (alphabet));
    for (int i=0; i<n; ++i)
            for (char c=0; c<alphabet; ++c)
                    if (i > 0 && c != s[i])
                            aut[i][c] = aut[pi[i-1]][c];
                    else
                            aut[i][c] = i + (c == s[i]);
}

vector<int> prefix_function (string s) {
        int n = (int) s.length();
        vector<int> pi (n);
        for (int i=0; i<n; ++i)
                for (int k=0; k<=i; ++k)
                        if (s.substr(0,k) == s.substr(i-k+1,k))
                                pi[i] = k;
        return pi;
}
vector<int> prefix_function (string s) {
        int n = (int) s.length();
        vector<int> pi (n);
        for (int i=1; i<n; ++i) {
                int j = pi[i-1];
                while (j > 0 && s[i] != s[j])
                        j = pi[j-1];
                if (s[i] == s[j])  ++j;
                pi[i] = j;
        }
        return pi;
}
vector<int> ans (n+1);
for (int i=0; i<n; ++i)
        ++ans[pi[i]];
for (int i=n-1; i>0; --i)
        ans[pi[i-1]] += ans[i];
string s; // входная строка
const int alphabet = 256; // мощность алфавита символов, обычно меньше
s += '#';
int n = (int) s.length();
vector<int> pi = prefix_function (s);
vector < vector<int> > aut (n, vector<int> (alphabet));
for (int i=0; i<n; ++i)
        for (char c=0; c<alphabet; ++c) {
                int j = i;
                while (j > 0 && c != s[j])
                        j = pi[j-1];
                if (c == s[j])  ++j;
                aut[i][c] = j;
        }
string s; // входная строка
const int alphabet = 256; // мощность алфавита символов, обычно меньше
s += '#';
int n = (int) s.length();
vector<int> pi = prefix_function (s);
vector < vector<int> > aut (n, vector<int> (alphabet));
for (int i=0; i<n; ++i)
        for (char c=0; c<alphabet; ++c)
                if (i > 0 && c != s[i])
                        aut[i][c] = aut[pi[i-1]][c];
                else
                        aut[i][c] = i + (c == s[i]);

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> prefix_function (string s) {
            int n = (int) s.length();
            ArrayList<Integer> pi (n);
            for (int i=0; i<n; ++i)
                    for (int k=0; k<=i; ++k)
                            if (s.substr(0,k) == s.substr(i-k+1,k))
                                    pi[i] = k;
            return pi;
    }
    ArrayList<Integer> prefix_function (string s) {
            int n = (int) s.length();
            ArrayList<Integer> pi (n);
            for (int i=1; i<n; ++i) {
                    int j = pi[i-1];
                    while (j > 0 && s[i] != s[j])
                            j = pi[j-1];
                    if (s[i] == s[j])  ++j;
                    pi[i] = j;
            }
            return pi;
    }
    ArrayList<Integer> ans (n+1);
    for (int i=0; i<n; ++i)
            ++ans[pi[i]];
    for (int i=n-1; i>0; --i)
            ans[pi[i-1]] += ans[i];
    string s; // входная строка
    const int alphabet = 256; // мощность алфавита символов, обычно меньше
    s += '#';
    int n = (int) s.length();
    ArrayList<Integer> pi = prefix_function (s);
    vector < ArrayList<Integer> > aut (n, ArrayList<Integer> (alphabet));
    for (int i=0; i<n; ++i)
            for (char c=0; c<alphabet; ++c) {
                    int j = i;
                    while (j > 0 && c != s[j])
                            j = pi[j-1];
                    if (c == s[j])  ++j;
                    aut[i][c] = j;
            }
    string s; // входная строка
    const int alphabet = 256; // мощность алфавита символов, обычно меньше
    s += '#';
    int n = (int) s.length();
    ArrayList<Integer> pi = prefix_function (s);
    vector < ArrayList<Integer> > aut (n, ArrayList<Integer> (alphabet));
    for (int i=0; i<n; ++i)
            for (char c=0; c<alphabet; ++c)
                    if (i > 0 && c != s[i])
                            aut[i][c] = aut[pi[i-1]][c];
                    else
                            aut[i][c] = i + (c == s[i]);
}