Алгоритмы и структуры данных

Алгоритм Бойера-Мура

Алгоритм поиска подстроки в строке. Он основан на идее использования информации о самом шаблоне для пропуска большого количества символов в тексте во время поиска.

Алгоритм:
1. Построение таблицы смещений.
2. Начинаем сравнивать символы шаблона и текста справа налево.
-Если символы совпадают, продолжаем сравнивать следующие пары символов.
-Если символы не совпадают, используем таблицу смещений для определения максимального смещения.
3. В случае неполного совпадения переносим шаблон на максимальное смещение по таблице смещений.
4. Повторяем шаги 2 и 3 до тех пор, пока не найдется полное совпадение или не достигнем конца текста.

Сложность: O(n/m)

www.tgoop.com/the_algorithms/4610

6.5K viewsNov 22, 2023 at 09:03

Алгоритм Бойера-Мура

Алгоритм поиска подстроки в строке. Он основан на идее использования информации о самом шаблоне для пропуска большого количества символов в тексте во время поиска.

Алгоритм:
1. Построение таблицы смещений.
2. Начинаем сравнивать символы шаблона и текста справа налево.
-Если символы совпадают, продолжаем сравнивать следующие пары символов.
-Если символы не совпадают, используем таблицу смещений для определения максимального смещения.
3. В случае неполного совпадения переносим шаблон на максимальное смещение по таблице смещений.
4. Повторяем шаги 2 и 3 до тех пор, пока не найдется полное совпадение или не достигнем конца текста.

Сложность: O(n/m)

BY Алгоритмы и структуры данных