во внутреннем цикле выполняется. Следовательно,

и .

Пришли к следующей ситуации :

Вычисляем . Видим, что условие ) во внутреннем цикле выполняется. Следовательно, вычисляется новое значение ; условие опять выполнено, вычисляем новое и на этот раз условие выполняется, снова вычисляем . Наконец внутренний цикл завершается, причиной завершения является невыполнение условия и поэтому . Итак, вычислено .

Оценим трудоемкость алгоритма.

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

или

Суммируя последнее неравенство по от до , получим Отсюда трудоемкость оценивается сверху величиной .

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

Изложенный ниже алгоритм строит переходную функцию

автомата где , , . Предполагаем, что функция откатов уже построена.

Для слова получим автомат, заданный диаграммой, изображенной на рис. 13.4.

Рис. 13.4.

Содержание Назад