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

[@MahachJordan]

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

[@professional2094]

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

[@xsomniator]

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

[@UbiycaCrabov]

Спасибки

[@dauletbiakhmet312]

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

[@dauletbiakhmet312]

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