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