•  

ГлавнаяРабота с текстом и строками → Алгоритм поиска подстроки в строке

Создано: 25.07.2010 20:03:59 · Исправлено: 25.07.2010 20:04:41 · Прочтений: 3087

{ **** UBPFD *********** by delphibase.endimus.com ****
>> алгоритм поиска подстроки в строке

Зависимости: SysUtils
Автор:       ALex2)
Copyright:   2)
Дата:        1 февраля 2003 г.
***************************************************** }

function BMSearch(StartPos: Integer; const S, P: string): Integer;
type
  TBMTable = array[0..255] of Integer;
var
  Pos, lp, i: Integer;
  BMT: TBMTable;
begin

  for i := 0 to 255 do
    BMT[i] := Length(P);
  for i := Length(P) downto 1 do
    if BMT[Byte(P[i])] = Length(P) then
      BMT[Byte(P[i])] := Length(P) - i;

  lp := Length(P);
  Pos := StartPos + lp - 1;
  while Pos <= Length(S) do
    if P[lp] <> S[Pos] then
      Pos := Pos + BMT[Byte(S[Pos])]
    else if lp = 1 then
    begin
      Result := Pos;
      Exit;
    end
    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(1, 'dsade', 'de')
// в данном примере ф-ия возвратит число 4
// 1 - это позиция с которой ищем подстроку в строке