Реферат: Алгоритмы поиска в тексте

if WCBeginsWith(Suffix, P) then MaxShift := i;

if P[i] = '?' then for j := 0 to 255 do BMT^[i-1][j] := 0

else for j := 0 to 255 do

begin

CurShift := MaxShift;

SetLength(Suffix, lp - i + 1);

Suffix[1] := Char(j);

Move(P[i + 1], Suffix[2], lp - i );

SufPos := WCFindRightmost(P, Suffix, lp - 1);

if SufPos <> 0 then

CurShift := i - SufPos;

BMT^[i-1][j] := CurShift;

end;

BMT^[i-1][Byte(P[i])] := 0;

end;

end;

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

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

Преимущество в быстродействии более сложного варианта алгоритма Бойера-Мура перед более простым вариантом сказывается, только если длина образца велика, и в тексте часто встречаются отдельные последовательности символов, содержащиеся в образце. Главное же достоинство более сложного варианта алгоритма заключается в возможности реализации регистронезависимого поиска и поиска по шаблону.