Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 233
Текст из файла (страница 233)
На этом доказательство корректности процедуры СОмРОте-Ркергх-Ргггчст!Огч можно считать завершенным. Корректность алгоритма Кнута-Морриса-Прагга Процедуру КМР-Млтснек можно рассматривать как видоизмененную реализацию процедуры Рп гте-АОтомлтогч-Млтснек, использующую префиксную функцию я для вычисления переходов между состояниями. В частности, докажем, что на г'-й итерации циклов Гог как процедуры КМР-Млтснек, так и процедуры Р!гч!те-Аитомлтом-Млтснек состояние ц имеет то же значение, что и при тестировании на равенство гп (в строке 1О процедуры КМР-Млтснек и в строке 5 процедуры Рггчгте-Аггтомлтогч-Млтснек). Поскольку ранее было показано, что процедура КМР-Млтснек имитирует поведение процедуры Р!гч!те-литОМАТОГч-Млтснек, корректность процедуры КМР-Млтснек следует из корректности процедуры Р!инте-АОтомлтон-Млтсиек (и вскоре станет понятно, почему в процедуре КМР-Млтснек необходима строка 12).
Прежде чем формально доказать, что процедура КМР-Млтснек корректно имитирует процедуру Р!гчгте-АггтОмлтОгч-Млтснек, давайте разберемся, как префиксная функция я замещает функцию переходов 6. Вспомним, что когда автомат поиска подстрок находится в состоянии ц и сканирует символ а = Т[!], он переходит в новое состояние 6(ц, а). Если а = Р[ц+ 1), так что а продолжает соответствовать образцу, то б(ц, а) = ц+ 1.
В противном случае а ф Р[ц+ 1), так что а не соответствует образцу, и О < 6(ц, а) < ц. В первом случае, когда а продолжает соответствовать, процедура КМР-МАТСНЕк переходит в состояние ц+ 1, не обращаясь к функции гс проверка в цикле нй11е в строке 6 дает значение Рлсзе, проверка в строке 8 дает тите и строка 9 увеличивает ц.
Функция я вступает в игру, когда символ а не соответствует образцу, так что новое состояние д(ц, а) либо представляет собой ц, либо находится слева от ц вдоль "хребта" автомата. Цикл згЫ!е в строках 6 и 7 процедуры КМР-Млтснн! итеративно проходит по состояниям в я*[ц], останавливаясь, либо когда входит !Обб Часть Гсн. Избранные темы в состояние, скажем, Ч', такое, что а соответствует Р[Чз + Ц, либо югда д' проходит весь путь вниз до нуля. Если и соответствует Р(~+ Ц, то строка 9 устанавливает новое состояние равным Ч'+1, что должно быть равно б(д, а) для корректной работы имитации.
Другими словами, новое состояние б(д, а) должно либо представляет собой состояние О, либо быть на единицу больше некоторого состояния в л'[Ч] Давайте взглянем на пример на рис. 32.7 и 32.11, где образец представляет собой Р = аЬаЬаса. Предположим, что автомат находится в состоянии л = 5; состояниями в к*[5] в убывающем порядке являются 3, 1 и О. Если следующий сканируемый символ — с, то, как легю видеть, автомат переходит в соспжние б(5, с) = 6 как в процедуре Р!ьг!те-Аотомлто!Ч-МАтснек, так и в процедуре КМР-МАТснЕк.
Теперь предположим, что вместо зтого очередным сканируемым символом является Ь, так что автомат должен перейти в состояние б(5, Ь) = 4. Выход из цикла иг1гйе в процедуре КМР-МАтсннк происходит после однократного выполнения строки 7, и автомат оказывается в состоянии 9' = зг[5] = 3. Поскольку Р[л'+ Ц = Р(4] = Ь, проверка в строке 8 возвращает ткг!е, и процедура КМР-МАтснек переходит в новое состояние д'+ 1 = 4 = б(5, Ь). Наюнец предположим, что следующий сканируемый символ — а, так что автомат должен перейти в состояние б(5, а) = 1. При первых трех выполнениях теста в строке 6 возвращается ткое.
В первый раз мы находим, что Р[6] = с ~ а, и процедура КМР-МАтснек переходит в состояние зг[5] = 3 (первое состояние в я*(5]). Во второй раз мы обнаруживаем, что Р(4] = Ь ~ а, и переходим в состояние зг[3] = 1 (второе состояние в я*[5]). В третий раз мы находим, что Р[2] = Ь ф а, и перемещаемся в состояние л[Ц = 0 (последнее состояние в я*[5]).
Выход из цикла зч)гйе осуществляется по достижении состояния л' = О. Теперь в строке 8 обнаруживается, что Р[л'+ Ц = Р[Ц = а, и в строке 9 автомат переходит в новое состояние д' + 1 = 1 = б(5, а). Таким образом, наше интуитивное представление заключается в том, что процедура КМР-МАтснек выполняет итерации по состояниям в л (9] в убывающем порядке, останавливаясь в некотором состоянии д, а затем, возможно, переходя в состояние д' + 1. Хотя может показаться, что требуется большое количество работы просто для имитации вычисления б(о, а), помните, что асимптотически процедура КМР-МАтснек ничуть не медленнее процедуры Ргьнте-АитомАтонМАтснек.
Теперь мы готовы формально доказать корректность алгоритма Кнута- Морриса-Пратта. Согласно теореме 32.4 после каждого выполнения строки 4 процедуры РггчгТЕ-АитомАТОгч-МАТСНЕк мы имеем д = сг(Т,). Следовательно, достаточно показать, что то же самое свойство выполняется и в случае цикла 1ог в процедуре КМР-МАтснек. Доказательство выполняется по индукции по числу итераций цикла. Изначально обе процедуры устанавливают д равным нулю при первом входе в соответствующие циклы 1ог. Рассмотрим итерацию г цикла гог процедуры КМР-МАтснек, и пусть д' — состояние в начале данной итерации цикла. Согласно гипотезе индукции д' = о.(Т, г).
Необходимо показать, что Ч = гг(Т,) в строке 10. (Строка 12 будет обработана отдельно.) !057 Глава 52. Поиск оодстрок Когда мы рассматриваем символ Т[1], наидлиннейшим префиксом Р, являющимся суффиксом Т,, является либо Р4+з (если Р[у'+ Ц = Т[1]), либо некоторый префикс (необязательно истинный и, возможно, пустой) Ра . Рассмотрим по отдельности три случая, когда а(Т;) = О, сг(Т;) = у'+ 1 и О < а(Тс) < у'.
Если о(Т,) = О, то Ро = с является единственным префиксом Р, являющимся суффиксом Т,. Цикл зв1зйе в строках 6 н 7 выполняет итерации по значениям в я'[у'], но хотя Ра Л Т, ~ для каждого у Е л"[у'], цикл никогда не находит у, такое, что Р[у + 1] = Т[з]. Цикл завершается, когда у достигает нуля, и, конечно, строка 9 не выполняется.
Следовательно, у = О в строке 1О, так что у = ст(Т;). ° Если сг(Тл) = у' + 1, то Р[у' + 1] = Т[7], и проверяемое в строке 6 цикла н ййе условие прн первом проходе оказывается ложным. Выполняется строка 9 и увеличивается значение у, так что после этого мы имеем у = у' + 1 = о(Т,). ° Если О < а(Т;) < у', то цикл звпйе в строках 6 и 7 выполняет по меньшей мере одну итерацию, проверяя в порядке убывания каждое значение у е я" [у'] до тех пор, пока не прекратит работу при некотором у < у'.
Таким образом, Рв является наидлиннейшим префиксом Рв, для которого Р[у+1] = Т[1), так что, когда цикл звпйе завершает работу, у+1 = о(Ра Т[в]). Поскольку у' = с (Т; ~), из леммы 32.3 следует, что сл(Тв зТ[г]) = п(Рв Т[г]), Таким образом, мы имеем у+ 1 = о(Рв Т[г]) = п(Т; ~Т[7']) = о(Тг) при завершении цикла зв(зйе. После того как строка 9 увеличивает значение у, имеем у = о(Т,). Строка 12 в процедуре КМР-Млтснпк является необходимой, поскольку в противном случае можно обратиться к Р[пз + 1] в строке 6 после того, как будет найдено вхождение Р.
(Рассуждение, что у = <т(Т, ~) при следующем выполнении строки 6, остается корректным в силу указания из упр. 32.4.8: 6(т, а) = б(я[гп], а), или, что эквивалентно, а(Ра) = сг(Р ( )а) для любого а Е Е.) Оставшаяся часть доказательства корректности алгоритма Кнута-Морриса-Пратга следует из корректности процедуры Е1Н1те-АОтомятон-Млтснлк, поскольку мы уже показали, что процедура КМР-МЛТСНКК имитирует поведение Г1Н1ТЕАптОмлтОН-МАтснек. Упражнения 32.4.1 Вычислите префиксную функцию для образца аЬаЬЬаЬЬаЬЬаЬаЬЬаЬЬ. 32.4.2 Найдите верхнюю границу размера а *[у] как функцию от величины у.
Приведите пример, показывающий, что ваша оценка не может быть улучшена. 1058 Часть Гтк Избранные теми 32.4З Объясните, как найти вхождения образца Р в текст Т, зная функцию к для РТ (т.е. для строки длиной т + и, полученной в результате конкатенации строк Р и Т). 32.4.4 Воспользуйтесь групповым анализом, чтобы показать, что время работы процедуры КМР-Млтснек равно 9(п).
32.4.5 Воспользуйтесь функцией потенциала, чтобы показать, что время работы процедуры КМР-Мятснек равно сэ(п). 32.4.6 Покажите, как улучшить процедуру КМР-Мятсннк, заменив функцию л в страке 7 (но не в строке 12) функцией я', рекурсивно определяемой для д = 1, 2,..., т — 1 следующим образом: О, если л[д] = О, зг [д] = я'[зг[д]], если зг[д] ~ О и Р[я[д] + 1] = Р[д+ 1], зг[д], если я[д] ф О и Р[я[д] + 1] Зб Р[д+ Ц . Объясните, почему модифицированный алгоритм работает корректно, а также в чем состоит смысл этого улучшения.
32.4. 7 Разработайте алгоритм, который в течение линейного времени позволил бы определить, является ли текстовая строка Т циклическим сдвигом другой строки Т'. Например, строки атс и сат являются циклическими сдвигами одна другой. 32.4.й * Разработайте эффективный алгоритм вычисления функции переходов д для конечного автомата поиска заданного образца Р. Время работы алгоритма должно быть равно 0(т ]Е[). (Указаниег докажите, что б(д, а) = б(я[д], а), если д = тп или Р[д+ 1] ~ а.) Зидячн 32.1. Поиск лодензрок иа основе коэффициентов повторения Пусть у' обозначает строку, полученную конкатенацией з строк у. Например, (аЬ)з = аЬаЬаЬ.
Говорят, что строка х Е Е* имеет коэффициеизи ловнзорения (гереуйюп Гасгог) т, если х = у' для некоторой строки у б Е" и некоторого т > О. Пусть р(х) обозначает наибольшее т, такое, что х имеет коэффициент повторения т. Глаза 32 лоиск лодолрок 1059 а Разработайте эффективный алгоритм, принимающий в качестве входных данных образец Р[1..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
