Алгоритмы. Поиск подстроки. Алгоритм Рабина-Карпа

Программу данного курса вы можете посмотреть по ссылке - docs.google.com/document/d/1U...
В этой лекции мы рассмотрим задачу поиска подстроки используя алгоритм Рабина-Карпа. Этот алгоритм отличается особенной эффективностью при поиске множества подстрок (одинаковой длины) в строке. Рассмотрим реализацию этого алгоритма на некоторых языках программирования.
Ссылка на конспект этой лекции - drive.google.com/file/d/15a2S...
Ссылка на примеры кода - drive.google.com/drive/folder...
00:00 Вступление
01:00 Сведения о алгоритме Рабина-Карпа
02:09 Теоретическое описание алгоритма
03:16 Графическое объяснение алгоритма
06:08 Скользящая хеш-функция
16:17 Реализация на Python
20:18 Поиск множества подстрок одинаковой длины
21:36 Реализация на Java
29:49 Реализация на Fortran
33:56 Список литературы

[@radmitr]

Благодарю за шикарные лекции!

[@alextula3280]

Большое спасибо за ваш труд

[@user-bx9jn8fe9x]

19:05 25 строка. Справа от операции присваивания происходят арифметические манипуляции с current_hash, а затем от итогового результата вычисляется остаток от деления. Но current_hash - это уже результат остатка от деления gorner_schem на q (10 строка). Т.е. в данном алгоритме на каждой итерации происходит вычисление остатка от деления от остатка от деления и т.д.. Т.е. это не то же самое, что описано в предыдущих слайдах.

[@oleksandrtsymbaliuk]

Так на каждой итерации вы должны пересчитать хеш той части подстроки с которой работаете (подробнее 15 страница конспекта лекции) и именно это и происходит в 25. А 10 строка отвечает только за вычисление хеша и начальной части подстроки.

[@user-bx9jn8fe9x]

@@oleksandrtsymbaliuk в лекции Вы ничего не говорили про остаток от деления (на каждой итерации(!)), а тут вдруг он появился. И кроме того, если на каждой итерации происходит вычисление остатка от деления, то current_hash с пред. итерации ограничен q и есть вероятность уйти в отрицательные значения в первых фиолетовых скобках (после знака присваивания в выражении, в 25 строке). Стоит Вам уменьшить q до небольших значений, то вероятность этого сильно возрастет.

[@oleksandrtsymbaliuk]

@@user-bx9jn8fe9x Начиная со kzbin.info/www/bejne/Y5qxk2eVbs55hNU идет объяснение вычитание идет на каждой итерации именно с остатком от деления (как и указанно на слайде и в видео) и добавление нового значения (не зря же я на видео даже значки плюс и минус рисовал). А если вспомнить арифметику для деления по модулю, то станет понятно почему при вычитании и добавлении нужно вычислять остаток от деления. По поводу гипотетического ухода в отрицательные числа, а это то как получиться? Даже если получиться отрицательное число, то остаток от его деления на положительное а q положительное, даст обычное положительное число и ничего страшного не произойдет.

[@radmitr]

Функция `findSomeHash()` немного некорректно работает. Может быть так надо в конце? ```java public static int[] findSomeHash(int hash, int[] subHashs) { //... int[] result = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < subHashs.length; j++) { if (subHashs[j] == hash) { result[i++] = j; } } } return result; } ```

[@oleksandrtsymbaliuk]

Тут как раз все верно. Это же задача одновременного поиска множества подстрок, значит нужно определить не просто факт совпадения одного хеша (который из за коллизии может к тому же дать ложно положительный результат), а всех совпавших хешей (по сути всех подстрок хеши которых совпали с частью базовой строки). Значит нужно занести индексы всех нужных подстрок, и потом их всех проверить.

[@radmitr]

​@@oleksandrtsymbaliukАлександр, хотел всё-таки уточнить. Есть ли у вас группа в телеграмме? Или здесь лучше писать?

[@oleksandrtsymbaliuk]

Группа ? Нет, зачем она мне? Если есть вопросы, или замечания, то пишите в комментариях к видео. Я их периодически просматриваю, и когда есть возможность отвечаю.

[@radmitr]

@@oleksandrtsymbaliuk Допустим на входе функции: findSomeHash(111, [222, 222, 111]); Она должна вернуть [2] ? Возвращает [0] . Может так? Или я опять туплю ``` int[] result = new int[n]; int insertIndex = 0; for (int i = 0; i < subHashs.length; i++) { if (subHashs[i] == hash) { result[insertIndex++] = i; } } ```

[@oleksandrtsymbaliuk]

Да точно, тут вы правы. Спасибо за указанную неточность. Исправил.

[@radmitr]

2^64 - 1 или 2^63 - 1 ? "Awersome apple" => "Awesome apple"

[@oleksandrtsymbaliuk]

Добрый день. Тут опечатка на самом деле тут 2^61 - 1. Исправил.

[@radmitr]

Понял, спасибо! 2^31 - 1 = 2 147 483 647, следующее простое число Мерсенна: 2^61 - 1 = 2 305 843 009 213 693 951 @@oleksandrtsymbaliuk