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

 

Алгоритм:

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

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

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

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

Приведем две блок-схемы, описывающие алгоритм.

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

Рис. 1. Блок-схема: Алгоритм прямого поиска подстроки в строке

 

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

Рис. 2. Блок-схема: Алгоритм прямого поиска подстроки в строке

 

Пример 1: Строка S: на дворе трава, на траве дрова; подстрока P: траве.

Реализация алгоритма поэтапно показана на рис.3.

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

т

р

а

в

е

Рис.3. Работа алгоритма прямого поиска подстроки в строке для примера 1

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

Пример 2:

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

P: учитель

 

у

ч

и

т

ь

,

у

ч

и

т

ь

с

я

,

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

у

ч

и

т

е

л

ь

Рис.4. Работа алгоритма прямого поиска подстроки в строке для примера 2

6.4.2. БМ-поиск (Боуера–Мура)

 

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

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

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

 

Рис.5. Блок-схема БМ-поиска

 

Рассмотрим механизм сдвига на примере.

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

P: дрова

Начинаем сравнение с последнего символа образца. Символы, подвергшиеся сравнению, выделены: в строке – красным цветом, в образце – синим. Индекс k указывает на первый сравниваемый символ в строке S (первоначально k = M - 1), индексы i и j – на сравниваемые символы в образце и строке соответственно. Сначала i = M - 1, j = k, затем i и j уменьшаются на единицу, пока не произойдет несовпадение символов S [ j ] и P [ i ] либо не закончится образец (i = -1).

 

k

j

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

д

р

о

в

а

i

 

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

 

k

j

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

д

р

о

в

а

i

 

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

 

k

j

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

д

р

о

в

а

i

 

И опять не произошло совпадения образца со строкой. Теперь S [ k ] = ‘е’, такого символа в образце нет, поэтому мы можем сдвинуть образец сразу на его длину, т.е. увеличить индекс k на M.

k

j

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

д

р

о

в

а

i

 

Здесь S [ k ] = ’в’, расстояние от конца образца до символа ‘в’ равно единице, значит, индекс k увеличиваем на единицу.

 

k

j

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

д

р

о

в

а

i

 

Теперь S [ k ] = ’а’, такой символ в образце есть, но лишь в последней позиции, в остальной части образца его нет, поэтому увеличиваем индекс k на длину образца M.

 

k

j

н

а

д

в

о

р

е

т

р

а

в

а

,

н

а

т

р

а

в

е

д

р

о

в

а

д

р

о

в

а

i

Символа S [ k ] = ’ ’ в образце нет, увеличиваем индекс k на M.