Изменения

Здесь и далее считаем, что символы в строках нумеруются с <tex>10</tex>.

Определим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 1..\ldots i - 1} \{k : </tex> <tex>s[0 \ldots k - 1..k] = s[i - k + 1..\ldots i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>.

Наивный алгоритм вычисляет префикс -функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за <tex>n</tex>. Будем считать, что префикс-функция хранится в массиве <tex> p </tex>.

'''int'''[] prefixFunction('''string''' s): '''int'''[] p = '''int'''[s.length] fill(<tex>\pi</tex>p, 0) '''for''' i = 1 0 '''to''' ns.length - 1 '''for''' k = 1 0 '''to''' i- 1 '''if''' s[10..k] == s[i - k + 1..i] <tex>\pi</tex>p[i] = k '''return''' <tex>\pi</tex>p

*Заметим, что <tex>\pip[i + 1] \leqslant \pip[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>\pip[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>\pip[i + 1] - 1</tex>, следовательно неравенство <tex>\pip[i + 1] > \pip[i] + 1</tex> неверно.*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pip[i]</tex>, тогда, если <tex>s[i + 1] = s[\pip[i]]</tex>, то <tex>\pip[i + 1] = \pip[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[\pip[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = \pi(p[i) ] - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>\pi(p[i - 1)]</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(p[k)- 1]</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>\pi(p[i)]=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>\pi(p[i)]=0</tex>.

'''int'''[] prefixFunction('''string''' s): <tex>\pi</tex> p[10] = 0 '''for''' i = 2 1 '''to''' ns.length - 1 k = <tex>\pi</tex>p[i-1] '''while''' k > 0 '''and''' s[i] != s[k + 1] k = <tex>\pi</tex>p[k- 1] '''if''' s[i] == s[k + 1] k++ <tex>\pi</tex> p[i] = k '''return''' <tex>\pi</tex>p

Пусть мы хотим узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>p[i]</tex>: если <tex>p[i] =0</tex> , тогда в <tex>s[i]</tex> запишем новый символ, иначе <tex>s[i] = s[p[i]- 1]</tex>. Обратим внимание, что <tex>s[p[i]- 1]</tex> нам уже известно, так как <tex>p[i] - 1 < i</tex>.

s += s[p[i]- 1]

Пусть <tex>p</tex> {{---}} данная префикс-функция, <tex>s'</tex> правильная строка, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> {{---}} массив значений префикс-функции для <tex>s</tex>.

* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[1..0 \ldots n - 1] = q[1..0 \ldots n - 1]</tex>. Возможны два случая:

** <tex>p[n] > 0</tex>. По свойствам префикс-функции Бордер строки <tex> s'[0 \ldots n - 1] </tex> имеет длину <tex> p[n]-1] = s'q[n-1] </tex> {{---}} суффикс и префикс строки . Поэтому если дописать к строке <tex> s' </tex> длины символ <tex> ps[q[n] - 1] </tex> продолжаются одним символом, значит, надо на текущую позицию то бордер нашей новой строки <tex> s [0 \ldots n] </tex> поставить символ станет равен <tex> s[p[n]] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]]. Если значение  == Критерий корректности значений префикс-функции =={{Задача|definition = Дан массив значений префикс-функции увеличиваетсянекоторой строки <tex>s</tex>, значитнеобходимо проверить, текущим символом продолжается префикс длины корректен ли он за <tex> p[n - 1] O(|s|)</tex>. Так же узнать размер минимального алфавита, а из свойств следует, что при котором он корректен.}} === Решение ===Если выполняется неравенство <tex> 0 \leqslant p[n - i + 1] \geqslant leqslant p[ni] - + 1 </tex>, то мы можем построить строку из алгоритма выше, значит префикс-функция корректна. По предположению индукцию значение <tex> q[n  Найдем минимальный алфавит, при котором префикс- 1] </tex> будет вычислено вернофункция корректна. А если Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не увеличиваетсянуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву. === Доказательство корректности ===Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, значитчто для этого символа префикс-функция равна 0, символ т.к. мы добавили новую букву. Пройдемся циклом <tex> s[n] \mathrm{while}</tex> должен продолжить по подпрефиксам. Т.к. в меньшем решении буква не новая, то она увеличит подпрефикс и префикс -функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не существует алфаивта меньшей длинымощности, а в текущее значение префиксчем найденный алгоритмом выше. === Псевдокод === '''bool''' is_correct('''int'''[] p): '''for''' i = 0 '''to''' p.length -функции запишется как раз длина нового 1 '''if''' i > 0 && p[i] > p[Период_и_бордер,_их_связь#Определенияi - 1] + 1 ||бордераp[i] < 0 '''return''' '''false''' '''return''' '''true'''  '''int''' minimal_alphabet('''int'''[]p): c = 1 s[0]= 0 '''for''' i = 1 '''to''' p. Для этого будут использованы значения префиксlength -функции с меньшими индексами1 '''if''' p[i] == 0 '''fill'''(used, которые посчитаны верно, опять же по предположению индукции.false) k = p[i - 1] '''while''' k > 0 used[s[k]] = '''true''' k = p[k - 1] s[i] = -1 '''for''' j = 1 '''to''' c '''if''' !used[j] s[i] = j; '''break''' '''if''' s[i] == -1 s[i] = c++ '''else''' s[i] = s[p[i] - 1] '''return''' c

*[http://e-maxx.ru/algo/prefix_function MAXimal :: algo {{---}} :: Префикс-функция]