Изменения

Здесь и далее считаем, что символы в строках нумеруются с <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>.

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

p[10] = 0 '''for''' i = 2 1 '''to''' ns.length - 1

'''while''' k > 0 '''and''' s[i] != s[k + 1] k = p[k- 1] '''if''' s[i] == s[k + 1]

Дан массив с корректной [[Z-функция | Z-функцией ]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>.

Пусть Z-функция хранится в массиве <tex>z[0 \ldots n-1..n]</tex>. Префикс-функцию будем записывать в массив <tex>p[0 \ldots n-1..n]</tex>.

fill(p, 0) '''for''' i = 2 1 '''to''' z.length - 1

Пусть мы хотим узнать значение <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>.

'''for''' i = 1 0 '''to''' p.length- 1

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