Алгоритм Кнута-Морриса-Пратта (КМР)

При построении конечного автомата для поиска подстроки в тексте легко построить переходы из начального состояния в конечное принимающее состояние: эти переходы помечены символами подстроки (см. рис. 1). Проблема возникает при попытке добавить другие символы, которые не переводят в конечное состояние.

Рисунок 2.2.1 — Начало построения автомата для поиска подстроки hello.

Алгоритм Кнута-Морриса-Пратта основан на принципе конечного автомата, однако он использует более простой метод обработки неподходящих символов. В этом алгоритме состояния помечаются символами, совпадение с которыми должно в данный момент произойти. Из каждого состояния имеется два перехода: один соответствует успешному сравнению, другой — несовпадению. Успешное сравнение переводит нас в следующий узел автомата, а в случае несовпадения мы попадем в предыдущий узел, отвечающий образцу. Пример автомата Кнута-Морриса-Пратта для подстроки ababcb приведен на рисунке 2.

Рисунок 2.2.2 — Полный автомат КнуттаМорриса — Пратта для подстроки ababcb.

При всяком переходе по успешному сравнению в конечном автомате Кнутта-Морриса-Пратта происходит выборка нового символа из текста. Переходы, отвечающие неудачному сравнению, не приводят к выборке нового символа; вместо этого они повторно используют последний выбранный символ. Если мы перешли в конечное состояния, то это означает, что искомая подстрока найдена. Проверьте текст abababcbab на автомате, изображенном на рисунке 3, и посмотрите, как происходит успешный поиск подстроки. Ниже представлен полный алгоритм поиска:

subLoc = 1// указатель текущего сравниваемого символа в подстроке.

textLoc = 1// указатель текущего сравниваемого символа в тексте.

while textLoc <= length (text) and subLoc <= length (substring) do.

if subLoc = 0 or text[textLoc] = substring[subLoc] then.

textLoc = textLoc + 1.

subLoc = subLoc + 1.

else// совпадения нет; переход по несовпадению.

subLoc = fail[subLoc].

end if.

end while.

if (subLoc > length (substring)) then.

return textLoc — length (substring) + 1//найденное совпадение.

else.

return 0// искомая подстрока не найдена.

end if.

Прежде, чем перейти к анализу этого процесса, можно рассмотреть как задаются переходы по несовпадению. Можно заметить, что при совпадении ничего особенного делать не надо: происходит переход к следующему узлу. Напротив, переходы по несовпадению определяются тем, как искомая подстрока соотносится сама с собой. Например, при поиске подстроки ababcb нет необходимости возвращаться назад на четыре позиции при необнаружении символа c. На пятом символе в образце можно понять, что первые четыре символа совпали, и поэтому символы ab в тексте, отвечающие третьему и четвертому символам образца, совпадают также с первым и вторым символами образца.