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

Практика: 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: Период строки

Источник

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

Рассмотрим задачу, которая возникает каждый раз, когда вы делаете ctrl+f :

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

Как это поможет решить исходную задачу?

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

Такой алгоритм (посчитать префикс-функцию от \(s\#t\) и посмотреть, в каких позициях она равна \(|s|\) ) называется алгоритмом Кнута-Морриса-Пратта.

Как её быстро считать

Рассмотрим ещё несколько примеров префикс-функций и попытаемся найти закономерности:

Попытаемся решить задачу с помощью динамики: найдём формулу для \(p_i\) через предыдущие значения.

Z-функция

Немногого более простая для понимания альтернатива префикс-функции — z-функция.

\[ \underbracec\overbracedaba \hspace <1em>(z_4 = 3) \]

Как её быстро считать

Будем идти слева направо и хранить z-блок — самую правую подстроку, равную префиксу, которую мы успели обнаружить. Будем обозначать его границы как \(l\) и \(r\) включительно.

Сравнение

В целом они зет- и префикс-функции очень похожи, но алгоритм Кнута-Морриса-Пратта есть во всех классических учебниках по программированию, а про z-функцию почему-то мало кто знает кроме олимпиадных программистов.

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

Упражнение 1. Дан массив префикс-функции. Исходная строка не дана. Вычислите за \(O(n)\) зет-функцию этой строки.

Упражнение 2. Дан массив зет-функции. Исходная строка не дана. Вычислите за \(O(n)\) префикс-функцию этой строки.

Источник

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

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как 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).

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

Источник

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

понедельник, 31 октября 2011 г.

Алгоритм Кнута-Морриса-Пратта

По мотивам лекции Сагунова Данила и реализации indy256

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

Префиксом строки S называется подстрока строки S, первый символ которой совпадает с первым символом строки S.
Суффиксом строки S называется подстрока строки S, последний символ которой совпадает с последним символом строки S.
Длина префикса и суффикса строки S строго меньше длины строки S.
Префикс функция от строки S : П(S) – это максимальная длина префикса S, совпадающего с её суффиксом.
Z-функция от строки S – это массив длинной равной длине строки S, где Z[i] – это префикс функция от подстроки S, последний символ, которой равен S[i].

Пусть S = “abababaaabababac”
z[0] = П(“a”) = 0
z[1] = П(“ab”) = 0
z[2] = П(“aba”) = 1
z[3] = П(“abab”) = 2
z[4] = П(“ababa”) = 3
z[5] = П(“ababab”) = 4
z[6] = П(“abababa”) = 5
z[7] = П(“abababaa”) = 1
z[8] = П(“abababaaa”) = 1
z[9] = П(“abababaaab”) = 2
z[10] = П(“abababaaaba”) = 3
z[11] = П(“abababaaabab”) = 4
z[12] = П(“abababaaababa”) = 5
z[13] = П(“abababaaababab”) = 6
z[14] = П(“abababaaabababa”) = 7
z[15] = П(“abababaaabababac”) = 0

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

Ключевым моментов в функции подсчета Z-функции является цикл while(7-8 строки). На каждом шаге пытаемся увеличить длину префикса, равного суффиксу. Если это сделать не удается, то необходимо уменьшить размер префикса максимальным образом.

Рассмотрим нахождение z[7]. Текущая подстрока “abababaa”, z[6] = 5.
На шаге 7 пытаемся продолжить увеличивать длину префикса.
1) Сравниваем 5-ый символ с последним: ”ababa b a a ”
2) Необходимо максимальным образом уменьшить длину префикса. Для этого нужно найти префикс префикса, который обязательно будет равен суффиксу суффикса. П(”ababa”) = 3
3) Сравниваем 3-ый символ с последним: “aba b aba a ”. Продолжаем рассуждения пока префикс существует, т.е. пока имеет ненулевую длину, либо до совпадения концов префикса и суффикса. П(“aba”) = 1.
4) Сравниваем 1-ый символ с последним: “a b ababa a ”. П(“a”) = 0.
5) Сравниваем 0-ой символ с последним: “ a bababa a ”. Успех =)
Значит z[7] = 1.

Вернемся к исходной задаче поиска подстроки(S) в строке(TEXT). Если не хочется заморачиваться, а главное если есть такая возможность, то в общем случае можно получить строку TEXT’ = S + sep + TEXT, где sep – это символ, который гарантированно не встречается в строках S и TEXT, а “+” – это конкатенация строк. Затем найти z-функцию от TEXT’. Если z[i] = длина(S), значит S является подстрокой строки TEXT.

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

Более эффективная реализация:

Здесь сначала считается z-функция для строки S, а потом происходит эмуляция первой реализации, как будто строка S является префиксом строки TEXT. Как видно в данном случае затраты на память сократятся.

Источник

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

Возникла ситуация:
где бы я не читал разбор, немного непотно, как работает префикс-функция? Объясните, а что не пойму, попрошу изложить детальнее.

Префикс-функция
Пишу программу для реализации префикс функции. Возник ступор. Дана строка: aabaaabaa Какой.

код бредовый по-моему, но рабочий.
не пойму, что делает в нем k = p[k-1];

как я понял, из этого цикла можно выйти только кода k будет равен нулю:

потому как я проверял ручным способом и пытался найти такой текст при котором после k = p[k-1]
k все ещё было бы больше нуля и s[k] стало бы равно s[i], что привело бы выходу из цикла. но увы, не удалось,т.к. если, например, в какой-то момент k>0 и попадаем в этот цикл и, например, s[k] = ‘H’, то после выполнения k = p[k-1], k изменится, но s[k] так и останется равным ‘H’.

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

Добавлено через 42 минуты
Был не прав насчет кода, строку на википедии не совсем удачную выбрали, из-за чего неправильно понял алгоритм. В этой строке ‘aabaaab’ как раз учитывается тот момент, про который ругался в предыдущем посте. Для этой строки префикс-функция равна: [0,1,0,1,2,2,3] (смутить может предпоследняя цифра).

Добавлено через 1 час 5 минут
Dani предыдущий пост не воспринимай серьезно, там я неправильно написал да и код тоже неправильный из-за того, что не полностью понял алгоритм (кое какой момент смутил, как раз в том посте и ругался из-за него).
Вообщем, возьми строку «aabaaab», про которую писал выше и попробуй понять, как получить из неё префикс-функцию [0,1,0,1,2,2,3].

Префикс наименования переменных
изучаю код, пытаюсь приучить себя к стилю, разработчики используют префикс sz к типу LPCSTR, почему.

Заменить префикс “пере” на “при”
Если слово начинаетса с префикса “пере”, то заменить эго на “при”. помогите пожалуста=).

Источник