Разработка программы.

Задание
Запрограммировать поиск подстроки в строке используя метод Боуэра и Мура.


Решение
Этап 1. Разработка алгоритма
На каждой итерации алгоритм определяет вхождение подстроки в строку с текущей позиции либо определяет необходимый сдвиг для следующей итерации.
Алгоритм:
1. Установить смещение фрагмента относительно начала строки P=0.
2. Если достигнут конец строки, то перейти к шагу 9.
3. Определить символ строки над последним символом фрагмента.
4. По таблице расстояний определить необходимый сдвиг D.
5. Если D=0, то перейти к шагу 6; иначе установить P=P+D и перейти к шагу 3.
6. Проверить вхождение фрагмента в строку с текущей позиции.
7. Если нет вхождения, то установить P=P+D и перейти к шагу 3; иначе перейти к шагу 8.
8. Фрагмент входит в строку. Перейти к шагу 10.
9. Фрагмент не входит в строку. Перейти к шагу 10.
10. Конец алгоритма.

Этап 2. Описание структур данных
Вид данных Наименование показателя
Символьное обозначение
Тип данных Тип структуры
Входные Строка, в которой будет осуществляться поиск MainStr Строковый Строка
Входные Фрагмент, который необходимо найти в строке SubStr Строковый Строка
Выходные Количество попыток S Целочисленный Число
Промежуточные Текущее смещение подстроки относительно строки P Целочисленный Число
Промежуточные Расстояние D Целочисленный Число
Промежуточные Таблица расстояний Distance Целочисленный Массив


Этап 3. Описание метода решения
Поиск фрагмента осуществляется по алгоритму, описанному выше.
Перед началом поиска составляется таблица расстояний от конца фрагмента до каждой буквы (из одинаковых букв выбирается ближайшая к концу слова). Если буква в строку не входит, то указывается длина всего фрагмента. Таблица представляет собой массив байт (Distance), где номер элемента является номером буквы в системе кодировки ASCII.
Если, ведя поиск по алгоритму, обнаруживается, что символ строки над последним символом фрагмента равен ему (т.е. расстояние равно 0), то производится попытка определения вхождения фрагмента в строку с текущей позиции смещения. Если фрагмент входит в строку, то успешно завершаем поиск.
Если достигнут конец строки, а вхождение фрагмента не обнаружено, то завершаем поиск с выводом соответствующего сообщения.

Оглавление

Задание 3
Решение 3
Этап 1. Разработка алгоритма 3
Этап 2. Описание структур данных 3
Этап 3. Описание метода решения 4
Этап 4. Блок-схема алгоритма 5
Приложение А. Пример работы программы 6
Приложение B. Исходный текст программы 7
Литература 9

Литература

1. В. П. Некрасов Теоретическая информатика. Часть 2. Элементы дискретной математики
2. В. П. Некрасов Теоретическая информатика. Часть 3. Структуры данных
3. В. П. Некрасов Теоретическая информатика. Часть 4. Комбинаторные алгоритмы
4. Галисеев Г.В.. Программирование в среде Delphi 7. Самоучитель. М: Диалектика, 2004.
5. Мануйлов В.Г. Разработка программного обеспечения на Паскале М.: Изд-во ПРИОР, 1998.-238 с.
6. Павловская Т.А.. Паскаль. Программирование на языке высокого уровня. Питер, 2004.
7. Фленов М.Е. Библия Delphi.-СПб.: БХВ-Петербург,2007
8. Интернет-Университет Информационных Технологий http://www.INTUIT.ru Компонентный подход в программировании