АиСД S03E09. Строки. Хеширование. КМП. Z-функция

Алгоритмы и структуры данных. Семестр 3. Лекция 9.
На девятой лекции мы начали говорить о задаче поиска подстроки, рассмотрели алгоритмы Рабина-Карпа, Кнута-Морриса-Пратта и Z-алгоритм.
Университет ИТМО, 2021 г.

[@MahachJordan]

Обалденная лекция, написал сам алгоритм Рабина-Карпа! Спасибо, все доходчиво!

[@xsomniator]

Не совсем точно показан момент, когда находится pref(pref(s)) на 48:46. Красным надо отметить префикс и суффикс левой синей подстроки, а не строки s целиком. Да, этот же префикс будет и в правой синей подстроке, но это будет следствие из предыдущего шага.

[@professional2094]

спасибо! Очень круто!

[@user-kp1tc1zd2q]

Спасибки

[@dauletbiakhmet312]

я не понял как вероятность коллизии вышло n/m. Разве вероятность коллизии не равно количестно всевозможных различных строк длины m/количество различных значений хешфункции которое равно М(модулю по которому берутся хеши). количество различных строк длины m=26^m а количество различных чисел по модулю М равно самому М
Тогда вероятность равна m^26/M
Объясните плз где я ошибся

[@dauletbiakhmet312]

а я понял. мы рассматриваем не всевозможные строки длины м а всевозможные ПОДСТРОКИ строки s длины m их должно быть n-m+1 штук теперь ясно