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

Задание

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

Решение

Этап 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), то производится попытка определения вхождения фрагмента в строку с текущей позиции смещения. Если фрагмент входит в строку, то успешно завершаем поиск.

Если достигнут конец строки, а вхождение фрагмента не обнаружено, то завершаем поиск с выводом соответствующего сообщения.