Структуры данных и модели вычислений


Применение конечных автоматов в программировании - часть 2


Время работы этого алгоритма .

Пример.

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

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

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


Рис. 13.3. 

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

  1. Слова являются собственными префиксами и суффиксами слова .
  2. Последовательность

    обрывается на пустом слове.

  3. Любой префикс слова , являющийся его суффиксом, находится в последовательности

Пример.

Пусть . Тогда

Определение.

Функцией откатов для слова называют функцию , определяемую соотношением , где — префикс длины слова .

В нашем примере функция задается следующей таблицей:

Алгоритм Кнута-Морриса-Пратта построения функции откатов для слова :

Для разъяснения работы алгоритма рассмотрим ситуацию, возникшую при обработке слова на шаге . К этому моменту вычислены значения при :

Выполняем . Видим, что условие во внутреннем цикле не выполняется из-за первого сомножителя, так как , поэтому тело внутреннего цикла не выполняется, и далее в соответствии с алгоритмом вычисляем




Начало  Назад  Вперед



Книжный магазин