Изменения

Перейти к: навигация, поиск

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

114 байт добавлено, 15:11, 2 мая 2014
небольшой рефакторинг построения строки по префикс-функции
Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = \max\limits_{k = 1..i - 1} \{ 0, k : </tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>.
 
Здесь и далее считаем, что символы в строках нумеруются с <tex>1</tex>.
==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
'''for''' i = 0 '''to''' p.length - 1:
'''if''' p[i] == 0:
s += new charcharacter
'''else:'''
s += s[p[i]]
Пусть <tex>p</tex> данная префикс-функция, <tex>s'</tex> правильная строка, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> массив значений префикс-функции для <tex>s</tex>.
Докажем корректность индукцией по длине массива префикс-функции полученной строки.Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>.
* База очевидна для строки длиной <tex>1</tex>.
 
* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[1..n - 1] = q[1..n - 1]</tex>. Возможны два случая:
 <tex>1)</tex> ** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>. Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными. <tex>2)</tex> ** <tex>p[n] > 0</tex>. Предположим, что <tex>q[n] \neq p[n] </tex>. Заметим, что подстрока с <tex>1</tex> по <tex>p[n]</tex> оканчивается на <tex>n</tex>-ом символе. По предположению индукции наш алгоритм построил правильную строку до <tex>n - 1</tex> символа, следовательно, <tex>p[n] \leqslant q[n]</tex>. Представим, что <tex>q[n] > p[n] </tex>, тогда получается, что префикс с <tex>1..q[n]</tex> в строке <tex>s'</tex>, является подстрокой заканчивающийся на <tex>n</tex>-ом символе, но тогда возникает противоречие с тем, что массив <tex>p</tex> корректный. Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными. Простой пример некорректного <tex>p = {0,1,1} </tex>, тогда по алгоритму получится строка <tex>aaa</tex>. Очевидно, что префикс-функции не будут совпадать.
== Литература ==

Навигация