Изменения

Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = max \{ j k | j k < i,</tex> <tex>s[1..jk] = s[i - j k + 1..i] \}</tex>.

'''for''' j k = 1 '''to''' i - 1 '''if''' s[1..jk] == s[i - j k + 1..i] <tex>\pi</tex>[i] = jk

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

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