[Править]Переходы между состояниями [править]Прямые переходы

Пусть в нашем автомате пока одно состояние —  . Пройдем по образцу, добавляя для каждого его символа новое состояние и переход в него из предыдущего состояния по этому символу. Последнее состояние объявим допускающим. Таким образом, каждому состоянию теперь соответствует ровно один префикс образца. Пронумеруем их длинами соответствующих префиксов с увеличением на единицу.

[Править]Суффиксные ссылки

Теперь нужно расставить остальные переходы. В итоговом автомате при переходе в состояние   префикс образца —   — должен быть максимальным его префиксом, равным суффиксу текста до последнего просмотренного символа, включительно. Переходы, осуществляющие перемещение в такие префиксы, называют суффиксными ссылками.

В качестве базы построения суффиксных ссылок проведем из   по всем символам алфавита, кроме первого символа образца, ссылки в  : длина максимального текущего суффикса текста, равного префиксу образца, увеличивается максимум на один и только в том случае, когда очередные их символы совпадают. Пусть построены все переходы из состояний, номер которых меньше некоторого  . Тогда для того, чтобы определить направление ссылки из состояния   по символу  , нужно найти длину наибольшего префикса образца, из состояния которого по   ведет прямой переход (если таких префиксов нет, значит, символ прежде не встречался в образце — нужно перейти в  ).Префикс-функция, взятая многократно от   символа образца, позволяет перебрать все префиксы образца, равные суффиксу его первых   символов. Таким образом,  , где справа описан прямой переход либо переход из  . Так как все переходы из первых   состояний уже построены,   соответствует нужному состоянию.

Если забыть про разницу в построении прямых переходов и суффиксных ссылок, можно заметить, что переходы   решают поставленную задачу нахождения максимального суффикса текста, равного префиксу образца.

[Править]Псевдокод

Построение автомата:

/*s — образец

m - длина образца

— алфавит

— размер алфавита

— префикс-функция образца

элементы строк и массивов нумеруются с единицы*/

trans = array[m + 1][ ] // заполнен элементами null, содержит множество переходов

for i = 1 to m:

trans[i][s[i]] = i + 1 // вставили прямые переходы

for every char in :

if char != s[1]:

trans[1][char] = 1 // вставили все переходы из стартового состояния

for i = 2 to m + 1:

for every char in :

if char != s[i]:

trans[i][char] = trans[ ][char] // вставляем суффиксные ссылки

Поиск вхождений образца в тексте:

/*t — текст

n — длина текста

m — длина образца

qs — стартовое состояние

qf — допускающее, то есть последнее, состояние

trans — полученный выше массив переходов

элементы строк и массивов нумеруются с единицы*/

state = qs // текущее состояние

for i = 1 to n:

if state == qf:

yield i - m // вывод позиции в тексте, начиная с которой, в него входит образец

state = trans[state][t[i]]

if state == qf:

yield n - m + 1 // образец является суффиксом текста