Задача поиска в строке
7.2.1. Постановка задачи и «прямое» решение
В данном подразделе будет рассмотрена задача, существенно отличающаяся от задач поиска в таблицах, которым была посвящена большая часть предыдущего материала. Объединяющим здесь является само понятие поиска.
Задача поиска подстроки в строке ставится следующим образом. Дана строка 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).
Возникает ощущение, что количество выполненных операций явно избыточно, из неудачи сравнения извлекается слишком мало информации. Усилия, предпринятые несколькими исследователями по усовершенствованию поиска, привели к появлению двух совершенно непохожих алгоритмов, каждый из которых заметно лучше, чем прямой поиск.
Дата добавления: 2016-03-27; просмотров: 656;