Изменения
Нет описания правки
Внесем несколько важных замечаний:
*<tex>\pi(i)</tex> превосходит <tex>\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>\pi(i) = 1</tex>, если <tex>s[i] = s[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>
===Время работы===
С помощью метода потенциалов можно показать, что время работы <tex>O(n)</tex>. Потенциал величины <tex>k</tex> связывается с текущим ее значением в алгоритме. Начальное значение этого потенциала равно нулю. На каждой итерации цикла <tex>while</tex> значение <tex>k</tex> уменьшается, поскольку <tex>\pi(k) < k</tex>. Однако в силу Поскольку <tex>\pi(k) \ge 0</tex> значение этой переменной не бывает отрицательным. Также значение <tex>k</tex> изменяется не более чем на 1 внутри тела цикла <tex>for</tex>. Поскольку перед входом в цикл выполняется <tex> k < i</tex> и поскольку значение переменной <tex>i</tex> увеличивается в каждой итерации цикла <tex>for</tex>, справедливость неравенства <tex>k < i</tex> сохраняется (подтверждая тот факт, что соблюдается также неравенство <tex>\pi(i) < i </tex>. Каждое выполнение тела цикла <tex>while</tex> можно оплатить соответствующим уменьшение потенциальной функции, поскольку <tex>\pi(k) < k </tex>. Кроме этого значение потенциальной функции возрастает не более чем на 1, из-за этого амортизированная стоимость тела цикла <tex>for</tex> {{---}} <tex>O(1)</tex>. Так как количество итераций <tex>O(n)</tex>, и поскольку конечное значение потенциальной функции по величине не меньше, чем ее начальное значение, полное время работы в наихудшем случае равно <tex>O(n)</tex>.
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
