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