Тренировки по алгоритмам 4.0. Лекция 2: Хеши для строк

Как сравнить любые подстроки, строки за O(1) и как с помощью этого написать свой поисковик

[iworeushankaonce]

6:21 Background про полиномы
18:35 Совпадающие Подстроки
43:36 Теория для решения Основание Строки
45:41 Задача Основание Строки из дз
50:26 Какой суффикс?
54:26 Свой поисковик

[Ruslanpvbs]

Доступно, автор мастер своего дела, спасибо!

[bvwycno]

отличная лекция и идея сравнения строк!

[johnwild]

Наверное, это никто не увидит, или это уже рассмотрели в разборе ДЗ, но при решении задачи на сравнение подстрок ориентировался на решение в видео и наткнулся на одну проблему. Если мы добавляем пробел в начале строки, а в функцию передаются from1 и from2 без учёта новой длины строки, то они будут указывать не на те подстроки, а в функции не на те хэши. Чтобы компенсировать пробел нужно в функции isequal() везде убрать "- 1".

[gordinmitya]

значительные приятности это лекции Михаила ❤

[glnfddn]

Это было прекрасно. Почти полтора часа кайфа

[tnlcmmf]

на 43:35 почему хеш подстроки за O(K), разве его нельзя вычислять за O(1) по формуле h[from + len - 1] - h[from - 1] * x[len] раз у нас есть вычисленные хеши префиксов?