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

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, иначе алгоритм завершен (вхождение найдено).

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

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

P: траве.

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

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

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

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

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

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

P: учитель

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

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

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

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

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

P: дрова

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

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

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

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

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

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

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

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

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

Здесь индекс i = –1, следовательно, образец в строке найден.

В целом индекс k S[k] меняется следующим образом:

если символа S[k] в образце нет (кроме, может быть, последнего символа!), то k увеличивается на длину образца M;
если символ S[k] в образце есть и он не последний, то индекс k увеличивается на расстояние от конца образца до ближайшего символа S[k].

Разумеется, величины сдвигов вычисляются заранее и заносятся в таблицу TAB. Блок-схема для формирования таблицы TAB представлена на рис.3.

Рис.3.Блок-схема для формирования таблицы TAB:

Следует особенно отметить, что j < M – 1, так как TAB[P[M – 1]] должен быть равен M, а не нулю.

Далее достаточно очевидно, что образ в строке найден, если индекс j стал меньше нуля, и образ в строке не найден, если индекс i дошел до конца строки, т.е. стал больше или равен N (i может стать больше N, так как изменяется «скачками»).

Теперь можно привести блок-схему БМ-поиска(рис.4).

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

КМП-поиск (Кнута–Мориса и–Пратта)

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

Пусть в образце все буквы не совпадают с первой, например:

S: от топота копыт пыль по полю летит

P: поле

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

п <