Алгоритмы и структуры данных #15 | Substring search, алгоритм Рабина-Карпа, rolling hash function

Сегодня говорим про алгоритм Рабина-Карпа для решения задачи substring search. Обсудим rolling hash function, технику sliding window и использование "нестандартных" систем счисления для представления данных. Таймкоды: 00:00 Введение 00:50 Задача substring search 03:30 Подход sliding window 06:20 Необходимость хэширования для поиска 07:50 Rolling hash 12:15 Появление коллизий 13:25 Переход к другой системе счисления 15:00 Пример в base26 18:10 Проблема с длинными строками 19:15 Операция mod 21:00 Алгоритмы Монте-Карло и Лас-Вегас 23:00 Дополнительная оптимизация хэширования 25:00 Пример реализации Станьте спонсором канала, и вы получите доступ к эксклюзивным бонусам:    / @ilyabodrovkrukowski   Boosty:
Patreon:   / bodrovis   Аккаунт Ethereum (ETH), Arbitrum, Polygon, BNB, USDT, TRX, BUSD: 0x719C2d2bcC155c85190f20E1Cc3710F90FAFDa16 Исходный код
Канал Telegram:
Наш чат в Telegram:
Мой сайт: