Изменения

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