59
правок
Изменения
→Псевдокод
===Псевдокод===
void getT(string x, int t[]): emptyint i = 0 int j = t[0] = -1 while i < x.size() while j > -1 and x[i] != x[j] j = t[j] i++ j++ if x[i] == x[j] t[i] = t[j] else t[i] = jvoid aG(string x, string y): int l, t[x.size()] <font color=green>//предподсчет <tex>-</tex> вычисление массива <tex>t</tex></font> getT(x, t) for l = 1 x[l - 1] == x[l] l++ if l == x.size() l = 0 <font color=green>//поиск<tex>-</tex> вычисление позиций вхождения <tex>x</tex> в <tex>y</tex></font> int i = l int j = 0 int k = 0 while j <= y.size() - x.size() while i < x.size() and x[i] == y[i + j] ++i if i >= x.size() while k < l and x[k] == y[j + k] ++k if k >= l OUTPUT(j) j += i - t[i] if i == l k = max(0, k - 1) else if t[i] <= l) k = max(0, t[i]) i = l else k = l i = t[i]
==Асимптотика алгоритма==
