Андрей Боровский
Наверное, каждому, кто много работает за компьютером, знакома подобная ситуация: перелистывая страницы книги в поисках нужного фрагмента, невольно начинаешь думать о том, как вызвать команду «поиск по всему тексту». Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды. Эту проблему нельзя эффективно решить при помощи стандартных функций Delphi/Kylix, поскольку большинство средств разработки включает только малоэффективные средства. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону).
В этой статье рассматриваются два варианта наиболее эффективного алгоритма поиска в тексте – алгоритма Бойера-Мура. Мы также рассмотрим некоторые полезные расширения этого алгоритма.
Прежде, чем приступить к рассмотрению алгоритма Бойера-Мура, приведем простейший (и самый медленный) алгоритм поиска, называемый «методом грубой силы».
function Find(const S, P : String) : Integer;
var
i, j : Integer;
begin
Result := 0;
if Length(P) > Length(S) then Exit;
for i := 1 to Length(S) - Length(P) + 1 do
for j := 1 to Length(P) do
if P[j] <> S[i+j-1] then Break
else if j = Length(P) then
Result := i;
Exit;
end;
