18 (1108017), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Функция kmpАлгоритм КМП для подстроки P и текста Т эквивалентенвычислению префикс-функции для строки Q = P#T, где# – символ, заведомо не встречающийся в обеих строкахДлина максимального префикса Q, являющегося еёсуффиксом (т.е. значение префикс-функции),не превосходит длины PДопустимый сдвиг обнаруживается в тот момент, когдаочередное вычисленное значение префикс-функциисовпадает с длиной подстроки P (условие if (q == m))В явном виде объединенная строка не строится!Теорема 2. Функция kmp работает правильно.Формальное доказательство осуществляется по аналогиис доказательством Теоремы 1, где множества, подобныеEq-1, строятся для строки-текста, а не строки-образца.Свойства префикс-функции часто используются и в другихзадачах (кроме поиска подстроки в строке)Полезной оказывается Лемма 1: итерированиемпрефикс-функции можно найти все префиксы строки, 20являющиеся ее суффиксамиАлгоритм Кнута – Морриса – Пратта.

Время работыФункция prefix_func выполняет ≤ (m – 1) итераций цикла for.Стоимость каждой итерации можно считать равной O(1),а стоимость всей процедуры O(m).Каждая итерация цикла while (строки 7-8) уменьшает kУвеличивается k только в строке 10 не более одного разана итерацию цикла for (строки 6-11)Следовательно, операций уменьшения не больше, чемитераций цикла for, то есть ≤ (m – 1) на весь цикл иO(1) на итерацию в среднемАналогично, функция kmp выполняет ≤ (n – 1) итераций, и еестоимость (без учета вызова prefix_func) есть O(n).Следовательно, время выполнения всей процедуры O(m + n).21.

Характеристики

Список файлов лекций