Изменения
→Оптимизация
==Оптимизация==
Вносятся несколько важных замечаний:
*Следует заметить, что <tex>\pi(i) \le \pi(i-1) + 1</tex>. По определению префикс функции верно, что <tex>s[1..\pi(i)] = s[i - \pi(i) + 1..i]</tex>. Отсюда В частности, получается, что <tex>s[1..\pi(i) - 1] = s[i - \pi(i) + 1..i - 1]</tex>. Поскольку <tex>\pi</tex> это наибольший префикс равный суффиксу, то <tex>\pi(i - 1) \ge \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>.
