Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 214
Текст из файла (страница 214)
Итак, множество Ев 1 состоит из таких значений lс < о-1, что Рь ' ) Рв г и Рь+1 ~ Рв (последнее следует из того, что Р [й+ Ц = Р [о]). Таким образом, множество Ев 1 состоит из тех значений Ь е я' [о — Ц, для которых строку Рь можно расширить до строки Рь+и получив в результате истинный суффикс строки Рв. Глава 32. Поиск подстрок 1043 Следствие 32.7. Пусть Р— образец длиной т, а я — префиксная функция этого образца. Тогда при д = 2, 8,..., т 0 если Ес 1 = 9, ] 1+ шах[ 1с Е Ес 1) если Ес г ф 9.
Доказалсельслгво. Если множество Ес 1 пустое, то не существует значений гс Е е сг' [д — Ц (включая Й = О), для юторых строку Рь можно расширить до строки Рь+1 и получить собственный суффикс Рс, Следовательно, сг [д] = О. Если множество Е 1 не пустое, то для каждого значения й е Е 1 справедливы соотношения гс+ 1 < 9 и Рь+1 ~ Рс. Следовательно, из определения сг [9] мы имеем я[9] > 1+шах(й е Ес 1').
(32.7) Заметим, что я [д] > О. Обозначим г = я [д] — 1, так что г + 1 = я [9]. Поскольку г+ 1 > О, имеем Р [г + 1] = Р [9]. Кроме того, согласно лемме 32.6, г Е л' [д — 1]. Таким обРазом, г Е Ес ы так что г < гпах(к Е Ес 1') или, что эквивалентно, сг [д] < 1 + шах (1с е Ес 1) . (32.8) Объединение уравнений (32.7) и (32.8) завершает доказательство.
Теперь завершим доказательство того, что процедура Сомготе Ркев~х Р~л~с'пои корректно вычисляет функцию я. В этой процедуре в начале каждой итерации цикла 1ог в строках 4 — 9 выполняется равенство lс = я. [9 — 1]. Это условие обеспечивается строками 2 и 3 во время первого вхождения в цикл и остается справедливым в каждой успешной итерации благодаря строке 9. В строках 5-8 значение переменной lс изменяется таким образом, что становится корректным значение сг [9]. В цикле в строках 5-б выполняется поиск по всем значениям lс Е Е я' [д — 1], пока не будет найдено такое значение, для юторого Р [lс + 1] = Р [9]. В этот момент й является наибольшим значением в множестве Ес м поэтому, согласно следствию 32.7, величину я [9] можно положить равной 1с + 1. Если же искомое значение lс не найдено, в строке 7 выполняется присваивание й = = О.
Если Р [1] = Р [д], то мы должны присвоить значение 1 как й, так и я [д]; в противном случае переменную Й следует оставить неизменной, а величине сг [д] присвоить значение О. В любом случае в строках 7-9 величинам lс и я [д] присваиваются правильные значения. На этом доказательство корректности процедуры Сомготе Ридах Рглчспон можно считать завершенным.
Корректность алгоритма Кнута-Морриса-Пратта Процедуру КМР МАтснлк можно рассматривать как видоизмененную реализацию процедуры Рппте Аитомлтон МАтснек. В частности, мы докажем, 1044 Часть ЧП. Избранные темы что код в строках 6-9 процедуры КМР Млтснек эквивалентен строке 4 процедуры Рмтк АитомАтон МАтснек, в которой переменной д присваивается значение б(д, Т [1]). Однако вместо того, чтобы использовать сохраненную величину 6(д,Т [1]), она вычисляется по мере необходимости с помощью функции я.
Поскольку ранее было показано, по процедура КМР МАтСнен имитирует поведение процедуры Р!%те АБтОМАтОН МАтснек, корректность процедуры КМР МАтснек следует из корректности процедуры Р1н1те АитомАтон МАтснек (и вскоре станет понятно, почему в процедуре КМР МАтснен необходима строка 12). Корректность процедуры КМР Млтснеи следует из утверждения, что должно выполняться либо соотношение Б (д, Т [1]) = О, либо соотношение 6 (д, Т [1]) — 1 Е Е к" [д]. Чтобы проверить это утверждение, обозначим й = 6 (д, Т [1]). Тогда из определений функций 6 и <т следует, что Рь 1 РтТ [1]. Следовательно, либо Ь = = О, либо Ь ) 1 и (отбрасывая последний символ из Рь и ОТ [1]) Рь 1 1 Рц (в этом случае Ь вЂ” 1 Е к' [д]).
Таким образом, либо )с = О, либо /с — 1 Е к' [д], что и доказывает сформулированное выше утверждение. Доказанное утверждение используется следующим образом. Обозначим через д' значение, юторое принимает величина д в строке 6, и воспользуемся уравнением к' [д] = (й: Ь < д и Рь ~ Рц) из леммы 32.5 для обоснования итерации д — к [д], перечисляющей элементы множества (lс: Рь ) Р'~. В строках 6-9 путем проверки элементов множества я' [д'] в убывающем порядке определяется величина 6 Я,Т [1]).
Указанное утверждение используется в юде для того, чтобы начать работу с д = ф(Т; 1) = з (Т, 1) и выполнять итерации д — к [д] до тех пор, пока не будет найдено значение д, такое что д = 0 или Р [д+ Ц = = Т [1]. В первом случае 6 (д', Т [1] = О), а во втором — значение переменной д равно максимальному элементу множества Е', так что 6 (д', Т [1]) = д+1 согласно следствию 32.7. Строка 12 в процедуре КМР Млтснек необходима для того, чтобы избежать возможного обращения к элементу Р [т+ 1] в строке 6 после того, как будет обнаружено вхождение образца Р.
(Согласно указанию, приведенному в упражнении 32.4-6, аргумент, что д = и (Т; 1), остается справедливым во время следующего выполнения строки б: для любого а Е Е Б (тп, а) = Б (и [тп], а) или, что эквивалентно, и (Ра) = и (Р [ [а).) Остальная часть обоснования корректности алгоритма Кнута-Морриса-Пратга следует из корректности процедуры Г~нгге А(л'омАтон МАтснек, поскольку теперь должно быть понятно, что процедура КМР МАтснек просто имитирует ее поведение. Упражнения 32.4-1.
Вычислите префиксную функцию для образца аЬаЬЬаЪЬаЬЬаЬаЬЬаЬЬ (алфавит имеет вид Е = (а, Ь1). Глава 32. Поиск подстрок 1045 32.4-2. Найдите верхнюю границу размера я*[у] как функцию от величины д. Приведите пример, показывающий, что ваша оценка не может быть улучшена. 32.4-3. Объясните, как найти вхождения образца Р в текст Т, зная функцию и для РТ (те. строки длиной т+и, полученной в результате конкатенации строк Р и Т). 32.4-4.
Покажите, как улучшить процедуру КМР МАтсннк, заменив функцию я в строке 7 (но не в строке 12) функцией я', рекурсивно определяемой для д = 1, 2,..., т следующим образом: О если я [д] = О, я' [о] = з' [к [д]] если я [д] ~ О и Р [я [д] + Ц = Р [д + 1], я [а] если я [а] ~ О и Р [я [а] + 1] ~ Р [а + 1]. Объясните, почему модифицированный алгоритм работает корректно, а также в чем состоит смысл этого улучшения. 32.4-5. Разработайте алгоритм, который бы позволил в течение линейного времени определить, является ли текстовая строка Т циклической перестановкой другой строки Т'.
Например, строки агс и саг являются циклическими перестановками друг друга. * 32.4-6. Разработайте эффективный алгоритм вычисления функции переходов Б для конечного автомата поиска заданного образца Р. Время работы алгоритма должно быть равно О (т Д). (Указание: докажите, что б (д, а) = = б (я [д], а), если д = т или Р [д+ Ц ф а.) Задачи 32-1. Поиск подстрок на основе коэффициентов повторения Обозначим как у' строку, полученную в результате г-кратной конкатенации строки у с самой собой. Например, (аЬ) = аЬаЬаЬ. Говорят, что коэффициент ловторенил (геребйюп Гасюг) строки х е Е* равен г, если х = у" для некоторой строки у Е Е' и значения т > О.
Через р(х) обозначим наибольший из коэффициентов повторения х. а) Разработайте эффективный алгоритм, принимающий в качестве входных данных образец Р [1..т] и вычисляющий значение р (Р;) для 1 = 1, 2,..., т. Чему равно время работы этого алгоритма? б) Определим для произвольного образца Р [1..т] величину р' (Р) как шах1<;< р(Р;). Докажите„что если образец Р выбирается случайным образом из множества всех бинарных строк длиной т, то математическое ожидание р' (Р) равно О (1). Часть Чй. Избранные темы 1046 в) Покажите, что приведенный ниже алгоритм поиска подстрок юрректно находит все вхождения образца Р в текст Т [1..и] в течение времени 0 (р* (Р) и + ти).
иеРет1т!ОН МАтснек(Р, Т) 1 т — 1еидЯР) 2 и — 1еидй[Т) З Ь 1+р'(Р) 4 д~-О 5 в -О 6 и)п1е в < и — ти 7 беЫТ[в+д+Ц = Р[д+Ц 8 1Ьеп д -д+1 9 1Т д = ти 10 1Ьеп рпп1 "Образец обнаружен при сдвиге" в 11 Ы д = т или Т[в+ д+ Ц ~ Р[д+ Ц 12 Феп в — в+ шах(1, [д/1в)) 13 д ~- О Этот алгоритм был предложен Галилом (ОаИ) и Сейферасом (Яе(Гегав). Развивая зти идеи, они получили алгоритм поиска подстрок с линейным временем работы, использующий всего 0 (1) памяти, кроме необходимой для хранения строк Р и Т. Заключительные замечания Связь поиска подстрок с теорией юнечных автоматов обсуждается в книге Ахо (А)ю), Хопкрофта (Норсгой) и Ульмана (П!1шап) [5).
Алгоритм Кнута-МоррисаПратта [187) разработан Кнутом (Клеей) и Прапом (Ргап) и независимо Моррисом (Мотив); результаты своих исследований они опубликовали совместно. Алгоритм Рабина-Карпа был предложен Рабином (КаЫп) и Карпом (Катр) [175). Галил (Оай1) и Сейферас (Бе(Гегав) [1071 разработали интересный детерминистический алгоритм поиска подстрок с линейным временем работы, в ютором используется лишь 0 (1) памяти сверх необходимой для хранения образца и текста. ГЛАВА 33 Вычислительная геометрия Вычислительная геометрия — это раздел теории вычислительных систем, изучающий алгоритмы, предназначенные для решения геометрических задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
