299
правок
Изменения
→Псевдокод
==== Псевдокод ====
Для случая подпоследовательностей нечётной длины, т.е. для вычисления массива <tex>d_1[]</tex>, получаем такой код:
List d1(n)
l = 0, r = -1
for i = 0 to n
k = (i > r ? 0 : min(d1[l + r - i], r - i)) + 1
while i + k < n && i - k >= 0 && s[i+k] == s[i-k]
++k
d1[i] = k--
if i + k > r
l = i - k, r = i + k
Для подпоследовательностей чётной длины, т.е. для вычисления массива <tex>d_2[]</tex>, лишь немного меняются арифметические выражения:
List d2(n)
l = 0, r = -1
for i = 0 to n
k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1)) + 1
while (i + k - 1 < n && i - k >= 0 && s[i + k - 1] == s[i - k])
++k
d2[i] = --k
if i + k - 1 > r
l = i - k, r = i + k - 1
=== Тривиальный алгоритм ===
