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