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