Рефераты | Рефераты по информатике, программированию | Алгоритмы поиска в тексте |
Теперь напишем функцию, осуществляющую поиск.
|
function BMSearch( StartPos : Integer; const S, P : String; const BMT : TBMTable) : Integer; var Pos, lp, i : Integer; begin lp := Length(P); Pos := StartPos + lp –1; while Pos < Length(S) do if P[lp] <> S[Pos] then Pos := Pos + BMT[S[Pos]] else for i := lp - 1 downto 1 do if P[i] <> S[Pos – lp + i] then begin Inc(Pos); Break; end else if i = 1 then begin Result := Pos – lp + 1; Exit; end; Result := 0; end; |
Функция BMSearch возвращает позицию первого символа первого вхождения образца P в строке S. Если последовательность P в S не найдена, функция возвращает 0 (напомню, что в ObjectPascal нумерация символов в строке String начинается с 1). Параметр StartPos позволяет указать позицию в строке S, с которой следует начинать поиск. Это может быть полезно в том случае, если вы захотите найти все вхождения P в S. Для поиска с самого начала строки следует задать StartPos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение P в S, нужно задать StartPos равным значению «предыдущий результат плюс длина образца».
Хотя рассмотренный упрощенный алгоритм вполне пригоден с практической точки зрения (и часто применяется), нельзя не заметить, что результаты сравнений используются недостаточно эффективно. Действительно, на втором шаге, когда у нас совпали три символа, мы, зная, что последовательность “bad” встречается в образце только один раз, могли бы сразу сместить образец на всю его длину, а не на один символ. Теперь мы рассмотрим другой, немного более сложный вариант алгоритма Бойера-Мура, позволяющий учесть результаты предыдущих сравнений в случае частичного совпадения образца и подстроки. Прежде всего изменим принцип построения таблицы смещений. В этом варианте алгоритма таблица – двумерная, каждому символу образца соответствует один столбец таблицы, а каждой букве алфавита – одна строка. В ячейках таблицы содержатся значения смещений, на которые нужно сдвинуть образец, если при проверке данного символа образца обнаружено несовпадение и вместо искомого символа получен символ алфавита, соответствующий некоторой строке в таблице. Например, таблица последовательности “abdab” для нашего пятибуквенного алфавита будет выглядеть следующим образом:
