Изменения

*<tex>\pi(i+ 1)</tex> превосходит <tex>\pi(i-1)</tex> не больше чем на <tex>1</tex>. Действительно, если <tex>\pi(i+1) > \pi(i-1) + 1</tex>, тогда <tex>\pi(i+1) - 1 > \pi(i-1)</tex>, значит в <tex>\pi(i-1)</tex> не максимально возможное значение, получили противоречие.*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i-1)</tex> и <tex>s[\pi(i - 1) + 1] = s[i+ 1]</tex>, тогда очевидно <tex>\pi(i+1) = \pi(i - 1) + 1</tex>. Если же условие <tex>s[\pi(i - 1) + 1] = s[i+ 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex>kj</tex>, для которой верно <tex>\pi(i+1) = kj + 1</tex>. Когда мы найдем такое <tex>kj</tex> нам достаточно будет сравнить <tex>s[kj + 1]</tex> и <tex>s[i+ 1]</tex>, при их равенстве <tex>\pi(i+1) = kj + 1</tex> будет верно. Будем искать наше <tex>kj</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i+1) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>kj</tex>.*Для поиска <tex>kj</tex> нам стоит использовать равенство <tex>k j = \pi(k - 1j) + 1</tex>, когда <tex>s[kj+1] = s[i+1]</tex> ложно, взяв за исходное <tex> k j = \pi(i - 1) + 1</tex>, это позволит выбирать <tex>kj</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex> для любых <tex>x</tex>.

k j = <tex>\pi</tex>[i - 1] + 1 '''while''' k j > 0 && s[i] != s[kj + 1] k j = <tex>\pi</tex>[k - 1j] + 1

kj++ <tex>\pi</tex>[i] = kj