Задача поиска в строке

Постановка задачи и «прямое» решение

В данном подразделе будет рассмотрена задача, существенно отличающаяся от задач поиска в таблицах, которым была посвящена большая часть предыдущего материала. Объединяющим здесь является само понятие поиска.

Задача поиска подстроки в строке ставится следующим образом. Дана строка A, состоящая из n символов (строка поиска) и строка S из m символов (искомая подстрока-образец). Требуется определить, содержится ли образец S в строке поиска A. При положительном ответе надо вернуть номер позиции A, с которой начинается первое вхождение S, а в противном случае надо вернуть 0.

По сути дела, это именно та задача, которая выполняется по команде поиска в текстовых редакторах.

Мы не будем здесь использовать готовый строковый тип данных Паскаля или C, и тем более применять строковые функции, определенные для этих типов. Наша задача как раз в том, чтобы разобраться в работе функции поиска в строке. Будем рассматривать строки просто как массивы символов.

Очевидное «прямое» решение задачи состоит в том, чтобы посимвольно сравнивать массивы A и S, а в случае несравнения очередной пары символов сдвигать S на одну позицию вдоль A и начинать цикл сравнения заново. Ниже приведены описания соответствующих типов данных и определение функции поиска.

const

N =...; {Длина строки поиска}

M =...; {Длина подстроки-образца}

type

StringN = array[1..N] of Char;

StringM = array[1..M] of Char;

function StraightSearch(A: StringN; S: StringM): Integer;

var

i, j: Integer;

begin

i:= -1;

repeat

i:= i + 1; {Сдвиг на одну позицию по A}

j:= 1;

while (j <= M) and (A[i+j] = S[j]) do

{Цикл сравнения}

j:= j + 1;

until (j > M) or (i > N - M);

if j > M then

StraightSearch:= i + 1 {Успех}

else

StraightSearch:= 0; {Неудача}

end; {StraightSearch}

Оценим эффективность прямого решения. Худшим случаем для данного алгоритма является такая ситуация, когда несовпадение с образцом обнаруживается только на последнем символе образца. Примером такого случая могут служить строки A = ‘aaaaaa... aaa’ (n букв ‘a’) и S = ‘aaa... ab’ (m–1 буква ‘a’ и одна буква ‘b’). Очевидно, при этом начинать сравнение придется n – m + 1 раз, а цикл сравнения будет состоять из m итераций. Получаем оценку: T(n, m) = O(n×m).

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