Префикс-функция
Версия от 21:27, 12 июня 2012; Vasin (обсуждение | вклад)
Префикс-функция строки
— функция .Содержание
Алгоритм
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
Псевдокод
Prefix_function () = [0,..,0] for i = 1 to n for k = 1 to i - 1 if s[1..k] == s[i - k + 1..i] [i] = k return
Пример
Рассмотрим строку abcabcd, для которой значение префикс-функции равно
.Шаг | Строка | Значение функции |
---|---|---|
a | 0 | |
ab | 0 | |
abc | 0 | |
abca | 1 | |
abcab | 2 | |
abcabc | 3 | |
abcabcd | 0 |
Время работы
Всего
итераций цикла, на каждой из который происходит сравнение строк за , что дает в итоге .Оптимизация
Вносятся несколько важных замечаний:
- Следует заметить, что . По определению префикс функции верно, что . Отсюда получается, что . Поскольку это наибольший префикс равный суффиксу, то .
- Избавимся от явных сравнений строк. Для этого подберем такое , что . Делать это нужно следующим образом. За исходное нужно взять , что следует из первого пункта. В случае, когда символы и не совпадают, — следующее потенциальное наибольшее значение , что видно из рисунка. Последнее утверждение верно, пока , что позволит всегда найти его следующее значение. Если , то при , иначе .
Псевдокод
Prefix_function () [1] = 0 k = 0 for i = 2 to n while k > 0 && s[i] != s[k + 1] k = [k] if s[i] == s[k + 1] k++ [i] = k return
Время работы
Время работы алгоритма составит
. Для доказательства этого нужно заметить, что итоговое количество итераций цикла определяет асимптотику алгоритма. Теперь стоит отметить, что увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение . Внутри цикла значение лишь уменьшается, а из предыдущего утверждения получается, что оно не может суммарно уменьшиться больше, чем раз. Значит цикл в итоге выполнится не более раз, что дает итоговую оценку времени алгоритма .Литература
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.