ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
(СПбГУТ)
Факультет инфокоммуникационных Сетей и систем (иксс)
кафедра программной инженерии и вычислительной техники (пиивт)
Лабораторная работа №2.
«Методы поиска: поиск подстроки»
Дисциплина: «Алгоритмы и Структуры Данных»
Выполнили: Студент группы ИКПИ-92 Козлов Никита
Тюришев Матвей
Смирнов Дмитрий
Пурин Иван
Принял: к.т.н., доцент кафедры ПИиВТ
Дагаев А.В.
Алгоритм Кнута-Морриса-Пратта
Алгоритм Кнута-Морриса-Пратта (в дальнейшем КМП) основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки фактически известна пройденная часть строки, и можно вычислить некоторые сведения, с помощью которых затем быстро продвинуться по строке. Сдвиг подстроки выполняется не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов, что вычисляется заранее префикс-функцией для подстроки. В процессе работы префикс-функции сравниваются префиксы и суффиксы подстроки, вычисляя необходимый сдвиг – максимальная длина совпадающих префикса и суффикса. Стоит отметить, что суффикс и префикс могут пересекаться. В процессе поиска и при обнаружении несовпадения, обращение происходит за индексом префикс-функции последнего совпавшего элемента подстроки.
Пример работы
Дана подстрока ABCABD. Вычислим для неё префикс-функцию, сравнивая префиксы и суффиксы, записывая полученные значения в отдельный целочисленный одномерный массив.
Для 0 элемента подстроки значение всегда равно 0.
Для 1 элемента подстроки сравним префикс (желтый) и суффикс (красный). ABCABD – совпадения нет, значение равно 0.
Для 2 элемента подстроки: ABCABD. Не забываем, что префикс и суффикс могут пересекаться, однако, АB не равняется BC. Совпадения нет, значение = 0.
Для 3 элемента подстроки: ABCABD. Совпадение есть, сравнение дальше: ABCABD. Совпадения нет, при дальнейшем сравнении тоже, значение = 1.
Для 4 элемента подстроки: ABCABD. Не совпадает, сравнение дальше: ABCABD. Совпадают 2 элемента, при дальнейшем сравнении перемен не будет, значение = 2.
Для 5 элемента подстроки: ABCABD. Совпадения нет, при дальнейшем сравнении тоже, значение = 0.
В итоге, для ABCABD массив значений префикс-функции выглядит следующим образом: 000120.
После этого осуществляется сам поиск подстроки в строке ABCABCAABCABD. На первом шаге сравнивается ABCABD и ABCABC. Не совпадает элемент 5. Значение префикс-функции для предыдущего элемента = 2. Переносим всю подстроку вправо так, что она будет начинаться на 2 элемента левее места несовпадения, т.е., сдвигая на 2 элемента влево.
На втором шаге сравнивается ABCABD и ABCAAB. Не совпадает элемент 4. Значение префикс-функции для предыдущего элемента = 1. Переносим всю строку вправо так, что она будет начинаться на 1 элемент левее места несовпадения, т.е., сдвигая на 1 элемент влево.
На третьем шаге сравнивается ABCABD и AABCAB. Несовпадение на элементе 1. Значение префикс-функции для предыдущего элемента = 0. Переносим всю строку вправо так, что она будет начинаться на месте несовпадения, т.е., без сдвига.
На четвертом шаге сравнивается ABCABD и ABCABD. Совпадение, подстрока найдена.
Алгоритм Бойера-Мура
Алгоритм Бойера-Мура (в дальнейшем БМ) считается наиболее быстрым среди остальных алгоритмов поиска подстроки в строке. Сначала строится таблица смещений для искомой строки, после совмещается начало строки и подстроки. Проверка начинается с последнего символа, справа налево. В случае несовпадения последнего символа – смещение на величину из таблицы смещений. Если не совпадает непоследний символ – смещение на один символ вправо. Всё совпало – нужная строка найдена.
Пример работы
Сначала вычисляется таблица смещений для алфавита строки и подстроки, опираясь на наличие символов в подстроке. Вычисление происходит следующим образом: вычисляется удалённость элемента от конца. Однако существует несколько важных условий:
Для повторяющихся символов используется значение самого близкого к концу элемента.
Для символов, которых нет в подстроке, присваивается значение длины всей подстроки
Вычисление таблицы смещений для подстроки ABCABD и строки ABCAFDFABCABD. Алфавит – ABCDF.
Для символа A значение в таблице смещений = 2, поскольку в подстроке он удален от конца на две позиции.
Для символа В значение в таблице смещений = 1, поскольку в подстроке он удален от конца на одну позицию.
Для символа С значение в таблице смещений = 3, поскольку в подстроке он удален от конца на три позиции.
Для символа D значение в таблице смещений = 0, поскольку в подстроке этот символ и является концом.
После этого осуществляется сам поиск подстроки в строке ABCAFDFABCABD. На первом шаге сравнивается ABCABD и ABCAFD. Не совпадает символ 4, в основной строке находится элемент, которого нет в подстроке, сдвиг на всю длину подстроки так, чтоб подстрока начиналась с места несовпадения в строке.
На втором шаге сравнивается ABCABD и DFABCA