Изменения

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

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

8 байт добавлено, 11:26, 31 января 2015
Эффективный алгоритм
Вносятся несколько важных замечаний:
* Заметим, что <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]+ 1]</tex>, то <tex>p[i + 1] = p[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[p[i]+ 1]</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]</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]]
Анонимный участник

Навигация