АиСД S03E09. Строки. Хеширование. КМП. Z-функция
Рет қаралды 7,130
2 жыл бұрынАлгоритмы и структуры данных. Семестр 3. Лекция 9.
На девятой лекции мы начали говорить о задаче поиска подстроки, рассмотрели алгоритмы Рабина-Карпа, Кнута-Морриса-Пратта и Z-алгоритм.
Университет ИТМО, 2021 г.
@MahachJordan 7 ай бұрын
Обалденная лекция, написал сам алгоритм Рабина-Карпа! Спасибо, все доходчиво!
@professional2094 11 ай бұрын
спасибо! Очень круто!
@xsomniator 11 ай бұрын
Не совсем точно показан момент, когда находится pref(pref(s)) на 48:46. Красным надо отметить префикс и суффикс левой синей подстроки, а не строки s целиком. Да, этот же префикс будет и в правой синей подстроке, но это будет следствие из предыдущего шага.
@dauletbiakhmet312 Жыл бұрын
я не понял как вероятность коллизии вышло n/m. Разве вероятность коллизии не равно количестно всевозможных различных строк длины m/количество различных значений хешфункции которое равно М(модулю по которому берутся хеши). количество различных строк длины m=26^m а количество различных чисел по модулю М равно самому М Тогда вероятность равна m^26/M Объясните плз где я ошибся
@dauletbiakhmet312 Жыл бұрын
а я понял. мы рассматриваем не всевозможные строки длины м а всевозможные ПОДСТРОКИ строки s длины m их должно быть n-m+1 штук теперь ясно
Fluency - RPA for Advertising
Рет қаралды 5
Алгоритмы и структуры данных 5. Алгоритм Рабина-Карпа, префикс и z-функции, поиск подстроки в тексте
Лекторий ФПМИ
Рет қаралды 3,6 М.