Суффиксный массив

  1. [Сережа.K] С/C++
    1. Конструкторы и деструкторы
    2. Finalize через деструкторы
    3. public, private, struct, class, наследование
    4. свой модный вектор с unique!
    5. nth_element: стандартный метод, реализация через qsort за O(n)
  2. [Сережа.М] Суффиксный зоопарк
    1. Суффиксный массив за O(nlog2n) хешами
    2. Суффиксный массив за O(nlogn)
      1. Сортировка подсчетом
      2. Цифровая сортировка
      3. Суффиксы → циклические сдвиги
      4. Основная фаза: удвоение длины
    3. LCP
      1. Алгоритм Касаи для подсчета LCP за O(n)
      2. Проблемы в случае циклических сдвигов и периодичной строки
    4. Задачи на строки, решение деревом и массивом
    5. LCP любых двух за O(1): RMQ в массиве, LCA в дереве
      1. Поиск строки в тексте (строим структуру от текста, отвечаем на запрос-строку)
      2. Число различных подстрок
      3. Общая подстрока двух строк
      4. Общая подстрока k строк
      5. [skipped] Число подпалиндромов
      6. [skipped] Число общих подпалиндромов
      7. [skipped] k-я лексикографически общая подстрока
      8. [skipped] Найти самую длинную строку, которая встречается как подстрока хотя бы k раз