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

[@radmitr]

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

[@alextula3280]

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

[@ДмитрийВикторович-р7ц]

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

[@oleksandrtsymbaliuk]

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

[@ДмитрийВикторович-р7ц]

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

[@oleksandrtsymbaliuk]

@@ДмитрийВикторович-р7ц Начиная со 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