Что такое алгоритм Рабина-Карпа?

Алгоритм Рабина-Карпа — это алгоритм сопоставления строкового шаблона, который эффективно ищет вхождения шаблона в большом тексте. Он был разработан Майклом О. Рабином и Ричардом М. Карпом в 1987 году.

Алгоритм использует технику хеширования для сравнения хэш-значений шаблона и подстрок текста. Это работает следующим образом:

• Вычислите хэш-значение шаблона и первого окна текста.

• Продвигайте шаблон по тексту по одной позиции и сравнивайте хэш-значения.

• Если хеш-значения совпадают, сравните символы шаблона и текущего окна текста, чтобы подтвердить совпадение.

• Если есть совпадение, запишите позицию/индекс совпадения.

• Вычислите хеш-значение для следующего окна текста, используя скользящую хеш-функцию.

• Повторяйте шаги с 3 по 5, пока не будут проверены все позиции текста.

Прокатная хэш-функция эффективно обновляет значение хеш-функции для каждого нового окна, вычитая вклад первого символа в предыдущем окне и добавляя вклад следующего символа в новом окне. Это помогает избежать пересчета хэш-значения с нуля для каждого окна, что делает алгоритм более эффективным.

PHP-программа для алгоритма Рабина-Карпа для поиска по шаблону

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

Выход

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

Пояснение кода

Код PHP реализует алгоритм Рабина-Карпа для поиска по шаблону. Он принимает шаблон и текст в качестве входных данных и ищет вхождения шаблона в тексте. Алгоритм вычисляет хеш-значения для шаблона и первого окна текста. Затем он перемещает шаблон по тексту, сравнивая хэш-значения текущего окна и шаблона. Если значения хеш-функции совпадают, он дополнительно проверяет символы один за другим. Если совпадение найдено, он печатает индекс, в котором найден шаблон. Алгоритм использует скользящую хеш-функцию для эффективного обновления хеш-значения для каждого окна. Код демонстрирует использование алгоритма путем поиска шаблона «BC» в тексте «ABCABCABCABCABC».

Заключение

В заключение: программа PHP эффективно реализует алгоритм Рабина-Карпа для поиска по шаблону. Используя скользящую хеш-функцию и сравнивая хеш-значения, алгоритм эффективно ищет вхождения шаблона в более крупный текст. Программа правильно определяет индексы, где встречается шаблон в тексте, и выводит результаты. Благодаря четкой структуре и соответствующим хеш-расчетам программа демонстрирует функциональность и полезность алгоритма Рабина-Карпа для поиска по шаблону в PHP.