19:05 25 строка. Справа от операции присваивания происходят арифметические манипуляции с current_hash, а затем от итогового результата вычисляется остаток от деления. Но current_hash - это уже результат остатка от деления gorner_schem на q (10 строка). Т.е. в данном алгоритме на каждой итерации происходит вычисление остатка от деления от остатка от деления и т.д.. Т.е. это не то же самое, что описано в предыдущих слайдах.
@oleksandrtsymbaliuk6 ай бұрын
Так на каждой итерации вы должны пересчитать хеш той части подстроки с которой работаете (подробнее 15 страница конспекта лекции) и именно это и происходит в 25. А 10 строка отвечает только за вычисление хеша и начальной части подстроки.
@ДмитрийВикторович-р7ц6 ай бұрын
@@oleksandrtsymbaliuk в лекции Вы ничего не говорили про остаток от деления (на каждой итерации(!)), а тут вдруг он появился. И кроме того, если на каждой итерации происходит вычисление остатка от деления, то current_hash с пред. итерации ограничен q и есть вероятность уйти в отрицательные значения в первых фиолетовых скобках (после знака присваивания в выражении, в 25 строке). Стоит Вам уменьшить q до небольших значений, то вероятность этого сильно возрастет.
@oleksandrtsymbaliuk6 ай бұрын
@@ДмитрийВикторович-р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 Жыл бұрын
Да точно, тут вы правы. Спасибо за указанную неточность. Исправил.