Алгоритмы и структуры данных. Семестр 3. Лекция 9. На девятой лекции мы начали говорить о задаче поиска подстроки, рассмотрели алгоритмы Рабина-Карпа, Кнута-Морриса-Пратта и Z-алгоритм. Университет ИТМО, 2021 г.
Не совсем точно показан момент, когда находится pref(pref(s)) на 48:46. Красным надо отметить префикс и суффикс левой синей подстроки, а не строки s целиком. Да, этот же префикс будет и в правой синей подстроке, но это будет следствие из предыдущего шага.
я не понял как вероятность коллизии вышло n/m. Разве вероятность коллизии не равно количестно всевозможных различных строк длины m/количество различных значений хешфункции которое равно М(модулю по которому берутся хеши). количество различных строк длины m=26^m а количество различных чисел по модулю М равно самому М Тогда вероятность равна m^26/M Объясните плз где я ошибся
