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