Изменения

===Псевдокод=== '''void''' getT('''string''' x, '''int''' t[]):<font color=green>//функция, вычисляющая массив <tex>t</tex> для строки <tex>x</tex></font> '''int''' i = 0 '''int''' j = t[0] = -1 '''while''' i < x.size '''while''' j > -1 '''and''' x[i] <tex>\neq</tex> x[j] j = t[j] i++ j++ '''if''' x[i] == x[j] t[i] = t[j] '''else''' t[i] = j

'''voidvector''' aG('''string''' x, '''string''' y):<font color=green>//<tex>x</tex> {{---}} образец, <tex>y</tex> {{---}} текст</font> '''int''' l, '''int''' t[x.size] '''vector''' v <font color=green>//предподсчет этап предпосчета<tex/font>- getT(x, t) <font color=green>/tex> вычисление массива /вычисляем значение <tex>tl</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 <tex>\leqslant</tex> y.size - x.size '''while''' i < x.size '''and''' x[i] == y[i + j] ++i '''if''' i <tex>\geqslant</tex> x.size '''while''' k < l '''and''' x[k] == y[j + k] ++k '''if''' k <tex>\geqslant</tex> l '''OUTPUT''' v.pushBack(j) j += i - t[i] '''if''' i == l k = max(0, k - 1) '''else''' '''if''' t[i] <tex>\leqslant</tex> l k = max(0, t[i]) i = l '''else''' k = l i = t[i] '''return''' v