34.3-4*

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

34.3-5

Пусть образец Р содержит, наряду с символами из алфавита £, еще и символы пропусков (упражнение 34.1-5). Постройте конечный автомат, который отыскивает все вхождения такого образца Р в текст Г за время 0(Т).

34.4. Алгоритм Кнута - Морриса - Пратта

Теперь мы переходим к алгоритму для поиска подстрок, работающему за линейное время. Этот алгоритм, предложенный Кнутом, Моррисом и Праттом, работает за время 0(то + п). Такое ускорение достигается за счет того, что предварительно вычисляется не функция перехода 5[0..т, 1..£], а в £ раз меньший массив - «префикс-функция» 7г[1..то] (её вычисление производится за время 0(т)). Зная функцию 7г, можно вычислить S(q,a) для любого состояния q G { 0,1,..., т } и символа а с учётной стоимостью 0(1) (в смысле амортизационного анализа). Сейчас мы увидим, как это делается.

34.4.1. Префикс-функция, ассоциированная с образцом

Префикс-функция, ассоциированная с образцом Р, несёт информацию о том, где в строке Р повторно встречаются различные префиксы этой строки. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов (говоря в терминах простейшего алгоритма поиска) или обойтись без предварительного вычисления функции перехода (в терминах конечных автоматов).

К префикс-функции приводит следующий ход мыслей. Пусть простейший алгоритм ищет вхождения подстроки Р = ababaca в текст Т. Предположим, что для некоторого сдвига s оказалось, что q первых символов образца совпадают с символами текста, а в следующем символе имеется расхождение (рис. 34.9 (а), где q = 5). Стало быть, мы знаем q символов текста, от T[s+1] до T[s + g], и из этой информации можно заключить, что некоторые последующие сдвиги будут заведомо недопустимы. В примере на рис. 34.9, скажем, сразу видно, что недопустим сдвиг s+ 1, поскольку при этом сдвиге первый символ образца (буква а) окажется напротив s + 2-го символа текста, совпадающего со вторым символом образца, -

Рис. 34.9. Префикс-функция тг. (а) Образец Р = ababaca расположен так, что первые 5 букв образца совпадают с буквами в тексте Г (совпадающие буквы серые и соединены отрезками), (б) Исходя только из совпадения этих 5 букв, мы можем заключить, что сдвиг s+1 недопустим. Допустимость сдвига s + 2 не противоречит тому, что мы к данному моменту знаем о тексте, и отбросить этот сдвиг заранее нельзя, (в) Информацию о том, какие сдвиги заведомо недопустимы, можно получить, исходя только из образца Р. В нашем случае мы видим, что наибольший префикс строки Р, являющийся суффиксом Р$ [и отличный от всей Р5], имеет длину 3. На языке префикс-функций это означает, что 7г[5] = 3. В общем случае: если при проверке сдвига s первые q символов образца совпали с соответствующими символами текста, то следующий сдвиг, который надо проверять, равен s = s + (q - tr[q]).

а это буква b. А вот при сдвиге на s + 2 (рис. 34.9 (б)) первые три символа образца совпадают с тремя последними из известных нам символов текста, так что этот сдвиг априори отбросить нельзя. В общем случае хотелось бы уметь отвечать на такой вопрос:

Пусть= T[s + l..s + q]; каково наименьшее значение

сдвига s > s, для которого

где s + k = s + ql

Число s - это наименьшее значение сдвига, большее s, которое нельзя отбросить с порога, исходя из равенства T[s + l..s + q] = P[l..q]. Больше всего нам повезёт, если s = s + q: тогда мы можем не рассматривать сдвиги s+1, s+2,..., s+g- 1. И во всяком случае, при проверке нового сдвига s мы можем не рассматривать первые к символов образца: из формулы (34.5) мы знаем, что они заведомо совпадают с соответствующими символами в тексте.

Чтобы найти s, нам не нужно ничего знать о тексте Г: достаточно знания образца Р и числа q. Именно, T[s+ l..s + к] - суффикс строки Pq. Поэтому число к в формуле (34.5) - это наибольшее число к < q, для которого Рк является суффиксом Pq. Практически удобно хранить информацию именно об этом числе к - количестве символов, заведомо совпадающих при проверке нового сдвига s. Само значение s вычисляется по формуле s = s + (q - к).

Теперь дадим формальное определение. Префикс-функцией (prefix function), ассоциированной со строкой Р[1..то], называется функция 7Г: { 1, 2,..., тп } -> { 0,1,..., тп - 1 }, определенная следующим образом:

P[l..k] = T[s + l..s + к]

(34.5)

ir[q]

max{ к : к < q н Рк Z\ Pq}.

Иными словами, 7г[д] - длина наибольшего префикса Р, являющегося (собственным) суффиксом Рд. На рис. 34.10 (а) приведена префикс-функция для строки ababababca.

Алгоритм Кнута - Морриса - Пратта мы запишем в виде процедуры KMP-Matcher. Как мы увидим, KMP-Matcher можно рассматривать как усовершенствование алгоритма Finite-Automaton-Matcher. Процедура Compute-Prefix-Function, вызываемая алгоритмом KMP-Matcher, вычисляет префиксную

функцию 7Г.

KMP-Matcher(Т,Р)

1п \gets length[Т]

2m \gets length[Р]

3\pi \gets Compute-Prefix-Function(P)

4q \gets 0

5for i \gets 1 to n

6do while q>0 and P[q+1] \ne T[i]

7do q \gets \pi[q]

8if P[q+l]=T[i]

9then q \gets q+1

10if q=m

11then print Образец входит со сдвигом i-m

12q \gets \pi[q]

Compute-Prefix-Function(P)

1m \gets length[P]

2\pi[l] \gets 0

3k \gets 0

4for q \gets 2 to m

5do while k>0 and P[k+1] \ne P[q]

6do k \gets \pi[k]

7if P[k+l]=P[q]

8then k \gets k+1

9\pi[q] \gets k

10 return \pi

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

34.4.2. Время работы

Покажем, что время работы процедуры Compute-Prefix-Function есть 0(т). Для этого воспользуемся методом потенциалов в амортизационном анализе (глава 18).

Процедура Compute-Prefix-Function выполняет то- 1 итераций цикла в строках 4-9. Покажем, что учётную стоимость каждой