e-maxx_algo

Префикс-функция. Алгоритм Кнута- Морриса-Пратта

Префикс-функция. Определение

строкой). В частности, значение полагается равным нулю.

Математически определение префикс-функции можно записать следующим образом:

Например, для строки "abcabcd" префикс-функция равна: , что означает:

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

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

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

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

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

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

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

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

Тривиальный алгоритм

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

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;

}

Как нетрудно заметить, работать он будет за , что слишком медленно.

Эффективный алгоритм

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

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

Первое важное замечание — что значение не более чем на единицу превосходит значение для любого .

противоречию. Иллюстрация этого противоречия (в этом примере должно быть равно 3):

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

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

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

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

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

мы можем с уверенностью сказать, что , это иллюстрирует схема:

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

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

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

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

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

Итоговый алгоритм

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

длину , полагая её равной , и повторяем этот шаг алгоритма с начала.

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

Реализация

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

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

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

В итоге получилась крайне простая реализация построения автомата, работающая за .

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

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

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

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

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

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

после "скармливания" символа он перейдёт в состояние:

После этого автомату "скармливается" последний кусок, т.е. :

Итак, мы решили задачу для строк Грея, аналогично можно решить целый класс таких задач. Например, точно таким же методом решается следующая задача: дана строка , и образцы , каждый из которых задаётся следующим образом: это строка из обычных символов, среди которых могут встречаться рекурсивные вставки других

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

Требуется найти количество вхождений строки в каждую из строк .

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

по целым строкам . В общем-то, это просто более общий случай по сравнению с задачей о строках Грея.

Задачи в online judges

Список задач, которые можно решить, используя префикс-функцию:

● UVA #455 "Periodic Strings" [сложность: средняя]

● UVA #11022 "String Factoring" [сложность: средняя]

● UVA #11452 "Dancing the Cheeky-Cheeky" [сложность: средняя]

● SGU #284 "Grammar" [сложность: высокая]

Алгоритмы хэширования в задачах на строки

Алгоритмы хэширования строк помогают решить очень много задач. Но у них есть большой недостаток: что чаще всего они не 100%-ны, поскольку есть множество строк, хэши которых совпадают. Другое дело, что в большинстве задач на это можно не обращать внимания, поскольку вероятность совпадения хэшей всё-таки очень мала.

Определение хэша и его вычисление

Один из лучших способов определить хэш-функцию от строки S следующий:

h(S) = S[0] + S[1] * P + S[2] * P^2 + S[3] * P^3 + ... + S[N] * P^N

где P - некоторое число.

Разумно выбирать для P простое число, примерно равное количеству символов во входном алфавите. Например, если строки предполаются состоящими только из маленьких латинских букв, то хорошим выбором будет P = 31. Если буквы могут быть и заглавными, и маленькими, то, например, можно P = 53.

Во всех кусках кода в этой статье будет использоваться P = 31.

Само значение хэша желательно хранить в самом большом числовом типе - int64, он же long long. Очевидно, что при длине строки порядка 20 символов уже будет происходить переполнение значение. Ключевой момент - что мы не обращаем внимание на эти переполнения, как бы беря хэш по модулю 2^64.

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

const int p = 31;

long long hash = 0, p_pow = 1;

for (size_t i=0; i<s.length(); ++i)

{

//желательно отнимать 'a' от кода буквы

//единицу прибавляем, чтобы у строки вида 'aaaaa' хэш был ненулевой hash += (s[i] - 'a' + 1) * p_pow;

p_pow *= p;

}

В большинстве задач имеет смысл сначала вычислить все нужные степени P в каком-либо массиве.

Пример задачи. Поиск одинаковых строк

Уже теперь мы в состоянии эффективно решить такую задачу. Дан список строк S[1..N], каждая длиной не более

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

Обычной сортировкой строк мы бы получили алгоритм со сложностью O (N M log N), в то время как используя хэши,

мы получим O (N M + N log N).

Алгоритм. Посчитаем хэш от каждой строки, и отсортируем строки по этому хэшу.

vector<string> s (n);

//... считывание строк ...

//считаем все степени p, допустим, до 10000 - максимальной длины строк const int p = 31;

vector<long long> p_pow (10000); p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p;

//считаем хэши от всех строк

//в массиве храним значение хэша и номер строки в массиве s

vector < pair<long long, int> > hashes (n); for (int i=0; i<n; ++i)

{

long long hash = 0;

for (size_t j=0; j<s[i].length(); ++j)

hash += (s[i][j] - 'a' + 1) * p_pow[j]; hashes[i] = make_pair (hash, i);

}

// сортируем по хэшам

sort (hashes.begin(), hashes.end());

// выводим ответ

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

{

if (i == 0 || hashes[i].first != hashes[i-1].first) cout << "\nGroup " << ++group << ":";

cout << ' ' << hashes[i].second;

}

Хэш подстроки и его быстрое вычисление

Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S[I..J]. По определению имеем:

H[I..J] = S[I] + S[I+1] * P + S[I+2] * P^2 + ... + S[J] * P^(J-I)

откуда:

H[I..J] * P[I] = S[I] * P[I] + ... + S[J] * P[J],

H[I..J] * P[I] = H[0..J] - H[0..I-1]

Полученное свойство является очень важным.

Действительно, получается, что, зная только хэши от всех префиксов строки S, мы можем за O (1) получить хэш любой подстроки.

Единственная возникающая проблема - это то, что нужно уметь делить на P[I]. На самом деле, это не так

просто. Поскольку мы вычисляем хэш по модулю 2^64, то для деления на P[I] мы должны найти к нему обратный элемент в поле (например, с помощью Расширенного алгоритма Евклида), и выполнить умножение на этот обратный элемент.

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

Допустим, даны два хэша: один умноженный на P[I], а другой - на P[J]. Если I < J, то умножим перый хэш на P[J-I], иначе же умножим второй хэш на P[I-J]. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

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

string s; int i1, i2, len; // входные данные

//считаем все степени p const int p = 31;

vector<long long> p_pow (s.length()); p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p;

//считаем хэши от всех префиксов vector<long long> h (s.length()); for (size_t i=0; i<s.length(); ++i)

{

h[i] = (s[i] - 'a' + 1) * p_pow[i]; if (i) h[i] += h[i-1];

}

//получаем хэши двух подстрок

long long h1 = h[i1+len-1]; if (i1) h1 -= h[i1-1]; long long h2 = h[i2+len-1]; if (i2) h2 -= h[i2-1];

// сравниваем их

if (i1 < i2 && h1 * p_pow[i2-i1] == h2 || i1 > i2 && h1 == h2 * p_pow[i1-i2]) cout << "equal";

else

cout << "different";

Применение хэширования

Вот некоторые типичные применения хэширования:

●Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)

●Определение количества различных подстрок за O (N^2 log N) (см. ниже)

●Определение количества палиндромов внутри строки

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

Пусть дана строка S длиной N, состоящая только из маленьких латинских букв. Требуется найти количество различных подстрок в этой строке.

Для решения переберём по очереди длину подстроки: L = 1 .. N.

Для каждого L мы построим массив хэшей подстрок длины L, причём приведём хэши к одной степени, и отсортируем этот массив. Количество различных элементов в этом массиве прибавляем к ответу.

Реализация:

string s; // входная строка int n = (int) s.length();

//считаем все степени p const int p = 31;

vector<long long> p_pow (s.length()); p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p;

//считаем хэши от всех префиксов vector<long long> h (s.length()); for (size_t i=0; i<s.length(); ++i)

{

h[i] = (s[i] - 'a' + 1) * p_pow[i]; if (i) h[i] += h[i-1];

}

int result = 0;

// перебираем длину подстроки for (int l=1; l<=n; ++l)

{

//ищем ответ для текущей длины

//получаем хэши для всех подстрок длины l vector<long long> hs (n-l+1);

for (int i=0; i<n-l+1; ++i)

{

long long cur_h = h[i+l-1]; if (i) cur_h -= h[i-1];

//приводим все хэши к одной степени

cur_h *= p_pow[n-i-1]; hs[i] = cur_h;

}

// считаем количество различных хэшей sort (hs.begin(), hs.end());

hs.erase (unique (hs.begin(), hs.end()), hs.end()); result += (int) hs.size();

}

cout << result;