Рис. 34.6, занимающий целую страницу. Переводы слов, входящих в рисунок: input - вход, state - состояние.

Подпись:

Рис. 34.6. (а) Таблица переходов для конечного автомата, допускающего строки, оканчивающиеся на ababaca (и только их). Здесь О - исходное состояние, 7 - единственное допускающее состояние (зачернено). Если из г в j ведет стрелка, помеченная буквой а, это означает, что S(a,i) = j. Жирные стрелки, идущие слева направо, соответствуют успешным этапам поиска подстроки Р [если мы в состоянии j, то j последних прочитанных букв текста совпадают с j первыми буквами образца; если мы перешли из состояния j в состояние j + 1, то очередная буква текста также совпадает с очередной буквой образца - шансы найти образец растут!]. Стрелки, идущие справа налево, соответствуют неудачам [последние j букв текста совпадали с первыми j буквами образца, но очередная буква - не такая, как хотелось бы]. Не все стрелки, идущие справа налево, показаны на рисунке: если из состояния г не выходит стрелки, помеченной буквой а, то подразумевается, что 5(i, а) = 0. (б) Таблица переходов для того же автомата. Клеточки, соответствующие успешным этапам поиска (жирным стрелкам на диаграмме), выделены серым, (в) Результат применения автомата к тексту Г = abababacaba. Под каждым символом Г [г] записано состояние автомата после прочтения этого символа (иными словами, значение <*р(Т{)). Найдено одно вхождение образца (начиная с позиции 3).

Рис. 34.7 Подпись:

К доказательству леммы 34.2: если г = а(ха), то г а(х) + 1.

Рис. 34.8 Подпись:

К доказательству леммы 34.3. Из рисунка видно, что г = a(Pqa), где q = а(х) и г = а(ха).

и время, требуемое для вычисления функции перехода 6. Мы этим вскоре займёмся, но сначала докажем, что процедура Finite-Automaton-Matcher правильно находит все вхождения подстроки Т.

Как отмечалось выше, нам достаточно показать, что для всех г выполнено соотношение (34.4), то есть что после прочтения символа Г [г] автомат оказывается в состоянии а{ТЛ. Это вытекает из следующих двух лемм.

Лемма 34.2 (неравенство для суффикс-функции)

Для любых строки х и символа а имеем а(ха) а(х) + 1.

Доказательство.

Если а(ха) > а(х) + 1, то отбросим последний символ а от наибольшего суффикса ха, являющегося префиксом Р, и получим суффикс строки х, имеющий длину больше а(х) и являющийся префиксом Р - противоречие (см. рис. 34.7).

Лемма 34.3 (Рекуррентная формула для суффикс-функции)

Пусть q = ст(х), где х - строка. Тогда для любого символа а имеем а(ха) = a(Pqa).

Доказательство.

Лемма 34.2 гласит, что а(ха) д + 1. Поэтому значение а(ха) не изменится, если оставить от строки ха последние q + 1 символов, то есть заменить его на строку Pqa (напомним, что последние q символов строки х образуют слово Pq, так как а(х) = q (рис. 34.8).

Из леммы 34.3 немедленно вытекает

Теорема 34.4

Пусть (р - функция конечного состояния автомата для поиска подстроки Р[1..то]. Если Г[1..п] - произвольный текст, то

(p(Ti) = а(Тг)

для г = 0,1,..., п.

Доказательство.

Для г = 0 это соотношение очевидно. Лемма 34.3 и формула (34.3) для функции перехода показывают, что оно сохраняется при прочтении автоматом очередного символа.

В силу доказанной теоремы, автомат после прочтения г символов текста находится в состоянии q тогда и только тогда, когда Pq является самым длинным суффиксом строки Ti, являющимся

одновременно префиксом строки Р. В частности, q = га означает, что автомат только что прочёл подстроку Р. Это доказывает правильность алгоритма Finite-Automaton-Matcher.

34.3.3. Вычисление функции перехода

Функцию перехода S, соответствующую образцу Т[1..га], можно вычислить так:

Compute-Transition-Function(P,\Sigma)

1m \gets length[Р]

2for q \gets 0 to m

3do for (для) всех символов a \in \Sigma

4do k \gets \min(m+l, q+2)

5repeat k \gets k-1

6until P k \sqsupset P qa

7\delta(q,a) \gets k

8return \delta

Эта процедура вычисляет функцию S «в лоб»: циклы, начинающиеся в строках 2 и 3, перебирают все пары (q,a), а в строках 4-7 наибольшее значение к, при котором для данной пары (q, а) выполнено соотношение Рк □ Pqa, находится прямым перебором, начиная с наибольшего априори возможного значения к, то есть min(ra, q + 1).

Время работы этого алгоритма есть 0(га3£): в самом деле, два внешних цикла дают множитель га£, внутренний цикл repeat может выполняться не более га + 1 раз, и сравнение в строке 6 требует О (га) операций. На самом деле функцию перехода можно вычислить гораздо быстрее, за время 0(га£) (см. упр. 34.4-6). В этом случае время поиска образца длины га в тексте длины п будет 0(п + га£).

Упражнения

34.3-1

Постройте автомат для поиска подстроки Р = aabab и продемонстрируйте его работу на тексте Г = aaababaabaababaab. 34.3-2

Нарисуйте диаграмму переходов автомата для поиска подстроки Р = ababbabbababbababbabb (над алфавитом £ = {а, Ъ}). 34.3-3

Будем говорить, что Р - строка с уникальными префиксами (Р is nonoverlappable), если соотношение Р □ Pq возможно лишь при к = 0 или к = q. Как выглядит диаграмма переходов автомата для поиска подстроки с уникальными префиксами?