Алгоритм поиска подстроки в строке

Delphi , Синтаксис , Текст и Строки

Автор: ALex2
WEB-сайт: http://delphibase.endimus.com

{ **** 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 - это позиция с которой ищем подстроку в строке

Это реализация алгоритма Бойера-Мура в Delphi для поиска подстроки в строке. Алгоритм был впервые описан Робертом С. Бойером и Джеймсом С. Муром в 1977 году.

Алгоритм Бойера-Мура - это эффективный алгоритм поиска строки, который использует два таблицы: одну для хранения информации о паттерне, который ищется, и другую для хранения информации о тексте, который ищется.

Вот шаг за шагом, как работает код:

1. Определен функция BMSearch, которая принимает три параметра: StartPos - начальная позиция в строке, где поиск должен начаться; S - строка, которую нужно найти; и P - подстрока, которую нужно найти.
2. Declare two variables: Pos, which will store the position of the first occurrence of the substring in the string, and lp, which is used as a loop counter.
3. Алгоритм инициализирует две таблицы: BMT (Bad Match Table) и TBMTable. Таблица BMT хранит информацию о паттерне, который ищется, а таблица TBMTable хранит информацию о тексте, который ищется.
4. Алгоритм затем проходит через каждый символ в паттерне (P) и инициализирует таблицу BMT, установив все значения равными длине паттерна.
5. Затем алгоритм проходит через каждый символ в паттерне с правой стороны налево, обновляя таблицу BMT на основе того, происходит ли несовпадение или нет.
6. После инициализации таблиц, алгоритм устанавливает Pos равным начальной позиции плюс длину подстроки минус один.
7. Основной цикл затем ищет подстроку, сравнивая символы между строкой (S) и паттерном (P). Если происходит несовпадение, алгоритм adjusts Pos переменную на основе значения в таблице BMT, соответствующем символу, который вызвал несовпадение.
8. Если конец паттерна достигнут или совпадение найдено, алгоритм проверяет, была ли подстрока полностью совпадающей, сравнивая символы между строкой и паттерном. Если полное совпадение найдено, алгоритм возвращает начальную позицию (Pos) первого обнаружения подстроки в строке.
9. Код также включает в себя некоторые обработчики ошибок, такие как возвращение 0, если не было обнаружено ни одного совпадения подстроки в строке.

Пример использования:

BMSearch(1, 'dsade', 'de')

Это будет искать подстроку 'de' начиная с позиции 1 в строке 'dsade', и вернуть начальную позицию (4) первого обнаружения подстроки в строке.

Алгоритм Бойера-Мура имеет сложность времени O(n + m), где n - длина строки, которую нужно найти, а m - длина подстроки, которую нужно найти. Это делает его эффективным выбором для поиска больших строк.

Алгоритм поиска подстроки в строке, представленный в статье, использует алгоритм Бойера-Мура для быстрого нахождения первого вхождения подстроки в строку.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Текст и Строки ::