Строки-1, поиск подстроки (14 апреля)

  1. Определения: подстрока, суффикс, префикс, период
  2. Поиск подстроки в строке
    1. Префикс функция
    2. Z-функция
    3. Алгоритм Боера-Мура'77 (и его модификация Чжу-Такаоки'87!)
  3. Полиномиальный хеш строки
    1. Коллизии
    2. Алгоритм Рабина-Карпа
    3. LCP за [O(n2), O(1)]
    4. LCP хешами за [O(n), O(logn)]
    5. Суффиксный массив за O(nlog2n)
  4. Потоки: алгоритм mincost circulation за O(m*logU*Dijkstra) через capacity scaling