из этих итераций можно считать равной 0(1). Для этого в качестве потенциала будем рассматривать значение к в момент входа в цикл. Поскольку начальное значение к равно нулю, а последующие равны ir[q] 0, реальная стоимость (время выполнения) всех итераций оценивается суммой учётных стоимостей, если считать учётной стоимостью сумму реальной стоимости и изменения потенциала.

Реальная стоимость каждой итерации складывается из стоимости присваиваний в строке 6, присваивания в строке 8 и присваивания в строке 9. Поскольку ir[j] < j для всех j, при каждом присваивании в строке 6 потенциал уменьшается по крайней мере на 1, что компенсирует работу по выполнению действий в цикле while, если умножить потенциал на достаточно большую константу. Поэтому вклад цикла while в учётную стоимость есть 0(1); присваивания же в строках 8 и 9 выполняются не более, чем по разу каждое, и увеличивают потенциал не более чем на две единицы. Поэтому учётная стоимость каждой итерации цикла for есть 0(1), а стоимость всей процедуры есть 0(т).

Аналогичное рассуждение, в котором в качестве потенциала выбирается q, показывает, что время выполнения строк 5-12 процедуры KMP-Matcher есть О (га). Стало быть, время выполнения всей процедуры KMP-Matcher есть О (то + га). Это - выигрыш по сравнению с алгоритмом Finite-Automaton-Matcher, который даже при экономном вычислении функции 6 требует времени 0(то£ + га).

34.4.3. Префикс-функция вычисляется правильно

Начнем с важной леммы, показывающей, что, итерируя префикс-функцию, можно для данного q найти все такие к, что Pj~ является суффиксом Pq. Именно, для данного q положим

7г°[д] = д, а 7гг[д] = 7т[7Гг-1 [д]]) и 7rf[g] = 0 (такое t найдется, так как ir[j] < j для всех j; на этом месте итерации обрываются).

Лемма 34.5 (Лемма об итерациях префикс-функции) Пусть Р - строка длины то с префикс-функцией 7Г. Тогда для всех q = 1, 2,..., то имеем 7г*[д] = { к : Р □ Pq }.

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

Покажем сначала, что

вательности Pq, Рж[ч], Pv[-K[q\], является суффиксом предыдущего (и, следовательно, всех предыдущих).

есть

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

Рис.34.10. К лемме 34.5 (Р = ababababca, q = 8). (а) Функция тг, связанная со строкой Р. Имеем 7г[8] = 6, 7г[6] = 4, 7г[4] = 2, 7г[2] = 0, так что 7Г*[8] = {8,6,4,2,0}. (б) Сдвигая строку Р относительно самой себя слева направо, отмечаем моменты, когда префикс Рк С Р является суффиксом строки Pg (совпадающие символы выделены серым и соединены вертикальными отрезками; пунктирная линия нарисована справа от Pg). Это происходит при к = 8, 6, 4, 2, 0, что совпадает со множеством 7Г*[8].

Покажем теперь, что и наоборот, { к : Рк □ Pq } С 7г*[д]. Рассуждая от противного, обозначим через j наибольший элемент множества {к : Рк □ Pq} \ K*[q]. Очевидно, j < q; раз j не лежит в последовательности 7г*[д], то j попадает между двумя её членами: j > j > 7Г[j] для некоторого j £ тг*[д].

Обе строки Pj и Pji являются суффиксами Рд: первая - по выбору j, вторая - в силу соотношения (34.6). Стало быть, Pj □ Pji по лемме 34.1, и Pj является префиксом строки Р, который является (собственным) суффиксом строки Pji и имеет длину больше тгЦ], что противоречит определению функции тг.

Рис. 34.10 иллюстрирует доказанную лемму.

Лемма 34.6

Пусть Р - строка длины то с префикс-функцией тг. Тогда n[q] - 1 £ TT*[q - 1] для всех q = 1, 2,..., то. для которых n[q] > 0. Доказательство.

Если к = n[q] > 0, то Р □ Pq, откуда, отбрасывая последний символ, получаем, что Pk-i □ Pq-i- По лемме 34.5 это означает, что 7r[g] - 1 £ K*[q - 1].

Для q = 2, 3,..., то определим множества Eq-\ формулой

(словами: Eq-\ состоит из таких к, что Pk - суффикс Pq-i, и за ними идут одинаковые буквы Р[/г + 1] и P[q], так что Pk+i - суффикс

Следствие 34.7

Пусть Р - строка длины то с префикс-функцией тг. Тогда для всех q = 2, 3,..., то имеем:

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

Если г = 7r[g] 1, то P[r] = P[q]; кроме того (лемма 34.6), г - 1 £ n*[q - 1], так что г - 1 £ Eq-\. Отсюда ясно, что если Eq-\ пусто,

= { к : к £ тг*[д - 1] и Р[к + 1] = P[q] }

0,если Eq-i = 0;

1 + max{ к £ Eq-i }, если Eq-\ ф 0.

то ir[q] = 0, и что если Eq \ непусто, то 7r[g] 1 + max{, k £ Eq \ }. Осталось показать, что если к £ Eq-i, то ir[q] к-\-1 - но это ясно, поскольку в этом случае Pk+i есть суффикс Pq (как мы отмечали после определения Eq \.

Теперь мы можем завершить доказательство правильности процедуры Compute-Prefix-Function, всех q. Докажем индукцией по q следующее утверждение: при входе в цикл, начинающийся в строке 4, выполнено равенство к = ir[q - 1]. При q = 2 это обеспечивается присваиваниями в строках 2 и 3. Шаг индукции: пусть к = ir[q - 1] при входе в цикл, тогда нам достаточно доказать, что при выходе из цикла будет к = ir[q]. В самом деле, в строках 5-6 ищется наибольший элемент множества Eq-\; если это множество непусто (это равносильно тому, что Р[к + 1] = P[q] при выходе из цикла в строках 5-6), то после присваивания в строке 9 число к оказывается равным ir[q] ввиду следствия 34.7. Если же это множество пусто (по выходе из цикла в строках 5-6 оказалось к = 0 и Р[к + 1] ф -Р[д]), то оказывается 7г[д] = 0, что также верно (следствие 34.7).

34.4.4. Алгоритм КМР правилен

Доказательство правильности процедуры KMP-Matcher проходит по той же схеме, что и для процедуры Compute-Prefix-Function. Достаточно (индукцией по г) доказать такие утверждения:

• В момент исполнения строк 10-12 выполнено равенство q =

• Перед каждым исполнением тела цикла (строки 6-12) выполнено равенство

(здесь cr(Tj) - длина наибольшего префикса Р, являющегося суффиксом Tj).

Заметим, что при г = 1 второе утверждение верно. Покажем теперь, что при каждом г из второго утверждения следует первое. В самом деле, пусть при некотором г второе утверждение верно. Лемма 34.5 показывает, что в строках 6-7 перебираются в убывающем порядке элементы множества S = {к < т : Р □ Pq}, причем перебор обрывается либо при нахождении наибольшего к £ S, для которого Р[к + 1] = Г [г], либо при к = 0 и Р[1] ф Т[г\. В первом случае по выходе из цикла в строках 6-7 q равняется наибольшему к, для которого Pk □ Ti-i и Pk+i □ Гг-; ясно, что к + 1 = ст(Гг-), и после исполнения строки 9 значение к + 1 присваивается переменной q. Во втором случае по выходе из цикла в строках 6-7 имеем,

7Г[ТО],

если <t(T8 i) < тп; если <t(T8 i) = тп.