что такое префикс функция

Поиск подстроки. Алгоритм Кнута–Морриса-Пратта

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае. Прежде чем перейти к описанию алгоритма, необходимо рассмотреть понятие префикс-функции.

Префикс-функция строки π(S,i) – это длина наибольшего префикса строки S[1..i], который не совпадает с этой строкой и одновременно является ее суффиксом. Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. Для строки S удобно представлять префикс функцию в виде вектора длиной |S|-1. Можно рассматривать префикс-функцию длины |S|, положив π(S,1)=0. Пример префикс функции для строки «abcdabcabcdabcdab»:

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

Алгоритм вычисления префикс-функции на языке Python:

Покажем, что время работы алгоритма составляет О(n), где n=|S|. Заметим, что асимптотику алгоритма определяет итоговое количество итераций цикла while. Это так, поскольку без учета цикла while каждая итерация цикла for выполняется за время, не превышающее константу. На каждой итерации цикла for k увеличивается не более чем на единицу, значит максимально возможное значение k=n–1. Поскольку внутри цикла while значение k лишь уменьшается, получается, что k не может суммарно уменьшиться больше, чем n–1 раз. Значит цикл while в итоге выполнится не более n раз, что дает итоговую оценку времени алгоритма O(n).

Рассмотрим алгоритм Кнута-Морриса-Пратта, основанный на использовании префикс-функции. Как и в примитивном алгоритме поиска подстроки, образец «перемещается» по строке слева направо с целью обнаружения совпадения. Однако ключевым отличием является то, что при помощи префикс-функции мы можем избежать заведомо бесполезных сдвигов.

Источник

Практика: Z-функция и КМП

Z-функция

Материал позаимствован с сайта e-maxx.ru.

Определение

Примеры

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

Формальное определение можно представить в виде следующей элементарной реализации за \(O(n^2)\) :

Разумеется, эта реализация слишком неэффективна, перейдём теперь к построению эффективного алгоритма.

Эффективный алгоритм вычисления Z-функции

Для этого будем поддерживать координаты \(\boldsymbol<[l;r]>\) самого правого отрезка совпадения, т.е. из всех обнаруженных отрезков будем хранить тот, который оканчивается правее всего. В некотором смысле, индекс \(r\) — это такая граница, до которой наша строка уже была просканирована алгоритмом, а всё остальное — пока ещё не известно.

\(i > r\) — т.е. текущая позиция лежит за пределами того, что мы уже успели обработать.

Приведём пример такой ситуации, на примере строки «aaaabaa».

Таким образом, в качестве начального приближения для \(z[i]\) безопасно брать только такое выражение:

Таким образом, весь алгоритм представляет из себя два случая, которые фактически различаются только начальным значением \(z[i]\) : в первом случае оно полагается равным нулю, а во втором — определяется по предыдущим значениям по указанной формуле. После этого обе ветки алгоритма сводятся к выполнению тривиального алгоритма, стартующего сразу с указанного начального значения.

Алгоритм получился весьма простым. Несмотря на то, что при каждом \(i\) в нём так или иначе выполняется тривиальный алгоритм — мы достигли существенного прогресса, получив алгоритм, работающий за линейное время (действительно, на каждый символ мы «посмотрим», т.е. сравним его с каким-либо предыдущим всего один раз).

Упражнение №2: Поиск подстроки

Пусть даны две строки. Найти все вхождения второй строки в первую.

Упражнение №3: Количество разных подстрок

Найти число всех различных подстрок входящих в данную.

Упражнение №4: Период строки

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

Материал частично позаимствован с сайта тоже e-maxx.ru.

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

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

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

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

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

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

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

Поиск подстроки в строке. Алгоритм Кнута-Морриса-Пратта

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

Как уже упоминалось при описании алгоритма вычисления префикс-функции, если известно, что значения префикс-функции не будут превышать некоторой величины, то достаточно хранить не всю строку и префикс-функцию, а только её начало. В нашем случае это означает, что нужно хранить в памяти лишь строку \(s + \#\) и значение префикс-функции на ней, а потом уже считывать по одному символу строку \(t\) и пересчитывать текущее значение префикс-функции.

Итак, алгоритм Кнута-Морриса-Пратта решает эту задачу за \(O(n+m)\) времени и \(O(n)\) памяти.

Упражнение №5: Префикс-функция

Напишите префикс-функцию. Пусть заголовком ее будет def p_func(s, n):

Упражнение №6: Поиск подстроки

Пусть даны две строки. Найти все вхождения второй строки в первую с помощью алгоритма Кнута-Морриса-Пратта.

Упражнение №7: Поиск подстроки онлайн

Упражнение №8: Количество разных подстрок

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

Упражнение №9: Период строки

Источник