2. 9.2 Поиск с предварительным анализом

Алгоритмы, реализованные в этих программах, можно использовать для организации поиска в строке S небольшой длины, так как попытки повысить эффективность приведут к излишним накладным расходам. Для строки S большой размерности (потоковые данные для приложений мультимедиа) прямые алгоритмы поиска могут быть неэффективными. Положение можно исправить рассмотренными ниже алгоритмами поиска с предварительным анализом искомой подстроки.

Основу материала этого раздела составляет алгоритм КМП-поиска. Имя "КМП" является выборкой первых букв фамилий его создателей: Д. Кнута, Д. Мориса и В. Пратта. В основе алгоритма КМП-поиска лежит идея о том, что в процессе просмотра строки S с целью поиска вхождения в нее образца Р становится известной информация о просмотренной части. Работа алгоритма производится в два этапа.

1. Анализируется строка-образец Р. По результатам анализа заполняется вспомогательный массив смещений D.

2. Производится поиск в строке S с использованием строки-образца Р и массива смещений D.

Ниже приведена программа, реализующая алгоритм КМП-

Идея алгоритма БМ-поиска в том, что сравнению подвергаются не первые, а последние символы образца Р и очередного фрагмента строки S. Если они не равны, то сдвиг в строке S осуществляется сразу на всю длину образца. Если последние символы равны, то сравнению подвергаются предпоследние символы, и т. д. При несовпадении очередных символов величина сдвига извлекается из таблицы D, которая, таким образом, выполняет ключевую роль в этом алгоритме.

Заполнение таблицы происходит на основе конкретной строки-образца Р следующим образом. Размер таблицы определяется размером алфавита, то есть количеством кодов символов, которые могут появляться в тексте. В нашем случае мы отвели под таблицу D память длиной, равной длине кодовой таблицы ASCII. Таким образом, строки S и Р могут содержать любые символы. Первоначально все байты кодовой таблицы заполняются значением, равным длине строки-образца для поиска Р. Далее последовательно извлекаются символы строки-образца Р начиная с первого. Для каждого символа определяется позиция его самого правого вхождения в строку-образец Р. Это значение и заносится в таблицу D на место, соответствующее этому символу. 

1. Программа работы и последовательность выполнения

1. Создайте новый проект. Процессор – dsPIC33FJ256GP710.

2. Подключите необходимые библиотеки.

3. Подключите отладчик (симулятор), встроенный в среду MPLABIDE.

4. Разработать программу, выполняющую поиск в строке по алгоритму указанному в таблице в соответствии с номером варианта

№ Варианта	Алгоритм поиска	Задание
1	Прямой поиск	Находит все вхождения слова «мой» и копирует их 2 раза.
2	Прямой поиск	Находит все вхождения слова «ты» и заменяет их на слово «вы».
3	Прямой поиск	Находит все вхождения слова «дурак» и удаляет их их текста.
4	Прямой поиск	Находит все вхождения слова «мы» и копирует их 3 раза, все вхождения слова «вы» удаляет.
5	КМП	Находит все вхождения слова «мой» и копирует их 2 раза.
6	КМП	Находит все вхождения слова «ты» и заменяет их на слово «вы».
7	КМП	Находит все вхождения слова «дурак» и удаляет их их текста.
8	КМП	Находит все вхождения слова «мы» и копирует их 3 раза, все вхождения слова «вы» удаляет.
9	БМ	Находит все вхождения слова «мой» и копирует их 2 раза.
10	БМ	Находит все вхождения слова «ты» и заменяет их на слово «вы».
11	БМ	Находит все вхождения слова «дурак» и удаляет их их текста.
12	БМ	Находит все вхождения слова «мы» и копирует их 3 раза, все вхождения слова «вы» удаляет.

5. Открыть окно Watchи внести в него все регистры, которые используются в коде. В пошаговом режиме отладить код, контролируя изменение регистров в окнеWatch. После отладки программы, показать код и результаты работы программы преподавателю.

6. Создать блок схему программы.

7. Подготовить отчет.