УП_САОД_2003

Прямой поиск

Разберем алгоритм поиска, который будем называть прямым поиском строки.

Данный алгоритм заключается в посимвольном сравнении текста со словом. В начальный момент происходит сравнение первого символа текста с первым символом слова, второго символа текста со вторым символом слова и т.д. Если произошло совпадение всех символов, то фиксируется факт нахождения слова. В противном случае производится «сдвиг» слова на одну позицию вправо и повторяется посимвольное сравнение, то есть сравнивается второй символ текста с первым символом слова, третий символ текста со вторым символом слова и т.д. Эти «сдвиги» слова повторяются до тех пор, пока конец слова не достиг конца текста или не произошло полное совпадение символов слова с текстом (то есть слово найдено).

function DirectTxtSearch(var Wrd: TWrd;

var Txt: TText;

var Position: integer): boolean;

{Функция поиска слова Wrd в тексте Txt,}

{если слово найдено, то возвращает значение true}

{и позицию Position начала первого слова Wrd,}

{иначе - false и Position не изменяется}

var

i, {Индекс начала слова в тексте}

j: integer; {Индекс текущего символа слова}

begin

i := 0;

repeat

j := 1; i := i + 1;

{Осуществляем посимвольное сравнение}

while (j <= M) and

(Txt[i+j-1] = Wrd[j]) do

j := j+1;

until (j = M+1) or {Совпало все слово}

(i >= N-M+1); {Конец слова за концом текста}

{Оценка результатов поиска}

if j = M+1 then begin

DirectTxtSearch := true;

Position := i;

end else begin

DirectTxtSearch := false;

end;

Рисунок 35. Алгоритм прямого поиска в тексте

Этот алгоритм работает достаточно эффективно, если допустить, что несовпадение пары символов происходит после незначительного количества сравнений во внутреннем цикле. При достаточно большом множестве символов это довольно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, несовпадение будет обнаруживаться после одной или двух проверок. Тем не менее, в худшем случае алгоритм будет малоэффективен, так как его сложность будет пропорциональна O((N-M)*M).

Содержание