Изменения

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

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

2 байта убрано, 19:33, 4 сентября 2022
м
rollbackEdits.php mass rollback
Здесь и далее считаем, что символы в строках нумеруются с <tex>0</tex>.
Определим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 0 1 \ldots i - 1} \{k : </tex> <tex>s[0 \ldots k - 1] = s[i - k + 1 \ldots i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>.
==Наивный алгоритм==
Вносятся несколько важных замечаний:
* Заметим, что <tex>p[i + 1] \leqslant p[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>p[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>p[i + 1] - 1</tex>, следовательно неравенство <tex>p[i + 1] > p[i] + 1</tex> неверно.
* Избавимся от явных сравнений строк. Пусть мы вычислили <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>.
[[Файл:mprfx.jpg|800px]]
1632
правки

Навигация