59
правок
Изменения
→Псевдокод
'''while''' j <tex>\leqslant</tex> y.size - x.size
'''while''' i < x.size '''and''' x[i] == y[i + j] <font color=green>// если <tex>x[i] = y[i + j]</tex></font>
++i <font color=green>// тогда следующая тройка <tex>(i + 1, j, k)</tex></font>
'''if''' i <tex>\geqslant</tex> x.size
'''while''' k < l '''and''' x[k] == y[j + k]<font color=green>// если <tex>k < l</tex> и <tex>x[k] = y[j + k]</tex></font> ++k <font color=green>// тогда следующая тройка <tex>(i, j, k + 1)</tex></font> '''if''' k <tex>\geqslant</tex> l <font color=green>// если <tex>k = l</tex></font> v.pushBack(j) <font color=green>// тогда найдена подстрока в позиции j</font> j += i - t[i] <font color=green>// вычисляем новый сдвиг</font>
'''if''' i == l
k = max(0, k - 1) <font color=green>// если <tex>i = jl</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font>
'''else'''
'''if''' t[i] <tex>\leqslant</tex> l <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
k = max(0, t[i])
i = l
'''else''' <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
k = l
i = t[i]
