Изменения

Пройдем Пройдём по строке <tex>t</tex> и для текущего символа будем искать длину наибольшей общей подстроки, которая заканчивается в текущей позиции. Для этого будем поддерживать <tex>v</tex> {{---}} текущее состояние и <tex>l</tex> {{---}} текущую длину совпадающей части.<br>Изначально <tex>v = 0</tex>, <tex>l = 0</tex> {{---}} совпадение пустое. Рассматриваем текущий символ <tex>t_i</tex>. Если в автомате существует переход из текущего состояния по данному символу, то перейдем в новое состояние и увеличим длину <tex>l</tex> на <tex>1</tex>.<br>Если перехода не существует, то попробуем минимально уменьшить длину совпадающей подстроки: перейдем по суффиксной ссылке из <tex>v</tex> в новое состояние и примем <tex>l = \mathrm{len(v)}</tex>. Повторим операцию до тех пор, пока не найдем найдём переход. Если по суффиксным ссылкам мы дошли до состояния, в которое ведет ведёт суффиксная ссылка начальной вершины, то это значит, что символа <tex>t_i</tex> нет в строке <tex>s</tex>. В таком случае примем <tex>v = l = 0</tex>, после чего перейдем к следующему символу строки <tex>t</tex>.<br>