Запишем построенную таким образом функцию переходов в виде таблицы (Табл. 1):

0	1	2	3	4	5	6	7
a	1	1	3	1	5	1	7	1
b	0	2	0	4	0	4	0	2
c	0	0	0	0	0	6	0	0

Строки соответствуют входным символам, столбцы — состояниям автомата. Ячейки, соответствующие успешным этапам поиска (входной символ совпадает со следующим символом образца), выделены серым цветом.

Построим по таблице граф переходов автомата (Рис. 1), распознающего образец ababaca. Находясь в состоянии q и прочитав очередной символ а, автомат переходит в состояние (q,a). Обратим внимание, что его остов помечен символами образца (эти переходы выделены жирными стрелками).

Рис. 1

Здесь 0 — исходное состояние, 7 — единственное допускающее состояние (зачернено). Если из вершины i в вершину j ведет стрелка, помеченная буквой а, то это означает, что (i,a) = j. Отметим, что переходы, для которых (i,a) = 0, на графе переходов для его упрощения не обозначены. Жирные стрелки, идущие слева направо, соответствуют успешным этапам поиска подстроки Р — следующий входной символ совпадает с очередным символом образца. Стрелки, идущие справа налево, соответствуют неудачам — следующий входной символ отличается от очередного символа образца.

Ниже приведен результат применения автомата к тексту Т = abababacaba. Под каждым символом Т[г] записано состояние автомата после прочтения этого символа (иными словами, значение (Т_i )) (Табл. 2).

Найдено одно вхождение образца (начиная с позиции 3). Найденный образец в тексте помечен серым цветом. Черным цветом помечено допускающее состояние автомата (состояние с номером 7).

Часть 2. Экспериментальный анализ алгоритмов.

2.1. Суть эксперимента.

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

Имеется несколько текстовых файлов, содержащих 10000 записей вида:
строка
подстрока (имеющаяся в данной строке)
место вхождения
длина подстроки

с разными максимальными длинами строк и подстрок.

Алфавитом является 66 русских заглавных и строчных букв.

Пусть это будут строки длиной не более 10, 100, 250 символов.

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

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

· Каждый алгоритм запускается 5 раз, время выбирается наименьшее.

Стенд для эксперимента.

Процессор Intel Pentium IV 2,66Ггц

1024 МбОЗУ

Компилятор Borland Delphi Enterprise, version 6.0 (Build 6.163)

Фрагмент кода тестируемой программы приведем в листинге 7.

LoadFromFile('C:\String_250.txt'); {Происходит загрузка в массив} Tick:=GetTickCount; {Запоминаем текцщее значение переменной Tick} Poisk; {Процедура в которой происходит поиск 10000 раз} Tick:=GetTickCount-Tick; {Получаем разницу – время в миллисекундах} WriteLn('Za vremja ',Tick, ' ms');