Алгоритмы поиска в тексте Андрей Боровский
    Наверное, каждому, кто много работает за компьютером, знакома подобная ситуация: перелистывая страницы книги в поисках нужного фрагмента, невольно начинаешь думать о том, как вызвать команду "поиск по всему тексту". Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды. Эту проблему нельзя эффективно решить при помощи стандартных функций 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
    begin
    Result := i;
    Exit;
    end; end; Функция Find ищет подстроку P в строке S и возвращает индекс первого символа подстроки или 0, если подстрока не найдена. Хотя в общем случае этот метод, как и большинство методов грубой силы, малоэффективен, в некоторых ситуациях он вполне приемлем. Мы сами воспользуемся похожим алгоритмом при построении таблицы смещений для метода Бойера-Мура.
    Алгоритм Бойера-Мура, разработанный двумя учеными - Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Прежде чем рассмотреть работу этого алгоритма, уточним некоторые термины. Под строкой мы будем понимать всю последовательность символов текста. Собственно говоря, речь не обязательно должна идти именно о тексте. В общем случае строка - это любая последовательность байтов. Поиск подстроки в строке осуществляется по заданному образцу, т. е. некоторой последовательности байтов, длина которой не превышает длину строки. Наша задача заключается в том, чтобы определить, содержит ли строка заданный образец.
    Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге мы строим таблицу смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее мы совмещаем начало строки и образца и начинаем проверку с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. ............