Изменения
→Псевдокод
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
'''int[]''' calculate1('''string''' s): '''int''' l = 0 '''int''' r = -1 '''for''' i = 1 '''to''' n '''int''' k = 0 '''if''' i <= r k = min(r - i, d[r - i + l]) '''while''' i + k + 1 <= n '''and''' i - k - 1 > 0 '''and''' s[i + k + 1] == s[i - k - 1] k++ d1[i] = k '''if''' i + k > r l = i - k r = i + k '''return''' d1
Вычисление значений массива <tex>d2</tex>:
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
'''int[]''' calculate2('''string''' s): '''int''' l = 0 '''int''' r = -1 '''for''' i = 1 '''to''' n '''int''' k = 0 '''if''' i <= r k = min(r - i + 1, d[r - i + l + 1]) '''while''' i + k <= n '''and''' i - k - 1 > 0 '''and''' s[i + k] == s[i - k - 1] k++ d2[i] = k '''if''' i + k - 1 > r l = i - k r = i + k - 1 '''return''' d2
===Оценка сложности===
