Строки, базовые алгоритмы (10 марта 2016)

  1. LCP за O(n2)
  2. Задачи на хеши
    1. Общая идея #1: любые две строки можно сравнить на равенство за O(1)
    2. Общая идея #2: любые две строки можно сравнить на больше/меньше за O(logn) бинпоиском
    3. Суф.массив за O(nlog2n)
    4. Z-функция за O(nlogn) хешами
    5. Найти все периоды строки хешами
    6. Количество различных подстрок за [O(n2), O(n)]
    7. Самая длинная общая подстрока, содержащая не более K пробелов за [O(nlogn), O(n)]
    8. Найти максимальную по длине строку, которая входит строку S два раза без наложения [O(nlogn), O(n)]
  3. Задачи на префикс-функцию и Z-функцию, LCP
    1. Найти наибольшую общую подстроку за O(n2) (3 решения: префикс, Z, LCP)
    2. Найти подстроку в тексте с возможностью одной опечатки за O(n) (z-функция с начала, z-функция с конца)
    3. Найти все периоды строки Z-функцией
    4. Найти все периоды строки Prefix-функцией
    5. [не успеем] Лемма: если +i, +j, то +gcd(i,j)
    6. [не успеем] Для каждого префикса строки S проверить его периодичность
    7. [не успеем] Найти в тексте s слово a, за ним слово b так, чтобы расстояние между вхождениями было минимально
    8. [не успеем] Найти номер строки в её суффиксном массиве
  4. [не успеем] Ещё задачи на хеши
    1. [не успеем] Количество подпалиндромов строки за O(nlogn)
    2. [не успеем] Самый длинный подпалиндром за O(n)