Алгоритм прямого поиска подстроки в строке

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒

▷ Похожие статьи

1. Установить i на начало строки S, т.е. i = 0.

2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм завершен (вхождения нет).

3. Начиная с i -го символа s провести посимвольное сравнение строк S и p, т. е. S [i] и P [0], S [i+1] и P [1],…, S [ i + M – 1] и P [ M – 1].

4. Если хотя бы одна пара символов не совпала, то увеличить i и повторить шаг 2, иначе алгоритм завершен (вхождение найдено).

Приведем пример, иллюстрирующий этот процесс. Символы образца, подвергшиеся сравнению, выделены синим цветом. Здесь

S: на дворе трава, на траве дрова;

P: траве.

Приведем две блок-схемы, описывающие алгоритм. В первой блок-схеме используется дополнительная переменная flag, которая явно изменяет свое значение с 0 на 1 при обнаружении вхождения образца P в текст S.

Во второй блок-схеме используется тот факт, что при j = M мы дошли до конца образца P, тем самым обнаружив его вхождение в строку S.

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

S: учиться, учить, учитель

P: учитель

1.2.2. Алгоритм Боуера и Мура

Рассмотрим самый «плохой» для линейного поиска случай:

Подсчитаем для него число сравнений. Так как несовпадение символов происходит на последней букве образца, в каждом внешнем цикле производится сравнений. Так как образец находится в конце строки, число внешних циклов равно , то есть общее число сравнений есть . В 1975 году Р. Боуер и Д. Мур предложили алгоритм, который значительно укоряет обработку данного случая. Алгоритм носит название БМ-поиска.

В отличие от линейного поиска, сравнение в БМ-поиске начинается не с начала, а с конца образца . Кроме того, образец предварительно анализируется, и благодаря этому образец сдвигается не на один символ, а в общем случае на несколько. Рассмотрим механизм сдвига на примере.

на дворе трава, на траве дрова

дрова

Начинаем сравнение с последнего символа образца. Символы, подвергшиеся сравнению, выделены: в строке – красным цветом, в образце – синим. Индекс указывает на первый сравниваемый символ в строке (первоначально ), индексы и – на сравниваемые символы в образце и строке соответственно. Сначала , , затем и уменьшаются на единицу, пока не произойдет несовпадение символов и , либо не закончится образец ().

Совпадения не произошло при первом же сравнении, необходимо сдвинуть образец, то есть увеличить индекс . В БМ-поиске образец сдвигается так, чтобы «под» символом (в таблице) оказался совпадающий с ним ближайший к концу символ образца (иначе при совпадения и точно не произойдет). Значит, в данном случае сдвигаем образец на одну позицию вправо, то есть увеличиваем индекс на единицу.

Совпадения образца со строкой опять не произошло, сдвигаем образец. Теперь и расстояние от конца образца до символа в нем равно двум, значит, индекс увеличиваем на два.

И опять не произошло совпадения образца со строкой. Теперь , такого символа в образце нет, поэтому мы можем сдвинуть образец сразу на его длину, то есть увеличить индекс на .

Здесь , расстояние от конца образца до символа равно единице, значит, индекс увеличиваем на единицу.

Теперь , такой символ в образце есть, но лишь в последней позиции, в остальной части образца его нет, поэтому увеличиваем индекс на длину образца .

Символа в образце нет, увеличиваем индекс на .

Символа в образце нет, увеличиваем индекс на .

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США