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

Фецяк

Денис

КН-22-1

Варіант 15 в списку

Варіант 4 в контрольній роботі

(Алгоритм Байєра-Мура)

Алгоритм Бойера-Мура - це швидкий алгоритм для пошуку підстрічки у рядку, розроблений Робертом Бойером і Дж. Він використовує два масиви для ефективного визначення кількості зсувів, необхідних для збігу символів підстрічки і рядка. Ці масиви залежать від самої підстрічки і використовуються для швидкого визначення наступного зсуву від поточної позиції.

Алгоритм має наступні етапи:

1. Створення двох масивів - масив зсувів та масив поганих символів - для заданої підстрічки.
2. Пошук підстрічки у рядку шляхом порівняння символів з кінця підстрічки до його початку з символами у відповідній позиції рядка.
3. При знайденні неспівпадіння використовується інформація з двох масивів для наступного зсуву.
4. Повторення кроків, знаходження підстрічки або до закінчення рядка.

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

У цьому коді структура даних складається з двох масивів:

Масив offset - масив зсуву. Він містить значення зсувів для кожного символу алфавіту. Зсув визначає те, на скільки символів можна зсунути паттерн вправо, якщо він не співпадає з текстом.

Масив bad_char - масив для поганих символів. Цей масив містить значення зсувів для кожного символу в паттерні, який не співпадає з останнім символом знайденого збігу. Якщо підстрока, яка не співпадає з текстом, міститься в паттерні, то цей масив міститиме зсув, на який можна зсунути паттерн так, щоб ця підстрока співпадала з відповідними символами.

Тестові дані

Перший

    std::vector<std::string> numbers = { "1", "9", "2", "3", "4", "5", "6", "7", "8" };

    std::string pattern = "3";

[pic 1]

Рис.1(Результат першого тесту)

Другий

std::vector<std::string> numbers = { "123", "345", "931", "83", "63", "43", "132", "793", "358" };

    std::string pattern = "3";

[pic 2]

Рис.2(Результат другого тесту)

Третій

    std::vector<std::string> numbers = { "13", "53", "93", "23", "3", "63", "83", "93", "73" };

    std::string pattern = "3";

[pic 3]

Рис.3(Результат третього тесту)

Лістинг

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

int boyer_moore(std::string text, std::string pattern) {

    int n = text.size();

    int m = pattern.size();

    if (m == 0) {

        return 0;

    }

    // Масив зсуву

    std::vector<int> offset(256, m);

    for (int i = 0; i < m - 1; i++) {