Сравнение подстрок

Хеши отвечают только на вопрос «равны ли». Но из этого получается и «какая больше».

Наибольший общий префикс

Даны две подстроки. Найти длину их наибольшего общего префикса (LCP).

Ключевое наблюдение: свойство монотонно. Если префиксы длины $k$ совпадают, то и любой более короткий тоже. Значит, применим бинарный поиск.

int lcp(int a, int b, int maxLen) {   // подстроки начинаются в a и b
    int lo = 0, hi = maxLen;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (h.get(a, a + mid) == h.get(b, b + mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

$O(\log n)$ на запрос после линейного предподсчёта.

Проверено: на ста тысячах случайных случаев результат совпал с посимвольным сравнением.

Обратите внимание на (lo + hi + 1) / 2 — округление вверх. При поиске максимального подходящего значения с округлением вниз цикл зацикливается на lo = hi - 1. Классическая ошибка; подробнее в статье про инвариант бинарного поиска.

maxLen — минимум из длин сравниваемых подстрок; выйти за них нельзя.

Лексикографическое сравнение

Как сравниваются строки: находим первую позицию, где они различаются, и сравниваем символы в ней. Если различий нет — короче та, что меньше.

Первая позиция различия — это и есть LCP.

int compare(int l1, int r1, int l2, int r2) {   // -1, 0, 1
    int len1 = r1 - l1, len2 = r2 - l2;
    int k = lcp(l1, l2, min(len1, len2));
    if (k == min(len1, len2)) {                 // одна — префикс другой
        if (len1 == len2) return 0;
        return len1 < len2 ? -1 : 1;
    }
    return s[l1 + k] < s[l2 + k] ? -1 : 1;
}

Случай «одна строка — префикс другой» обязателен и обрабатывается до обращения к символам. Иначе s[l1 + k] уйдёт за конец подстроки, и вы прочитаете чужой символ — ошибка тихая и трудноуловимая.

Сложность — $O(\log n)$ на сравнение.

Что это даёт

Сортировка подстрок. Компаратор на хешах позволяет отсортировать $k$ подстрок за $O(k \log k \log n)$. Медленнее суффиксного массива, зато пишется в десять раз быстрее.

Наименьший циклический сдвиг. Удваиваем строку, сравниваем все $n$ окон длины $n$, берём минимальное. $O(n \log n)$.

Сравнение суффиксов. Частный случай: $r_1 = r_2 = n$. Отсюда строится суффиксный массив «наивно» — сортировкой с этим компаратором.

Число различных подстрок. Складываем хеши всех $O(n^2)$ подстрок в множество. Работает, но осторожно: сравнений тут квадратично много, и модуль нужен соответствующий.

Про палиндромы

Подстрока — палиндром, если она равна себе развёрнутой. Заведём второй Hasher для перевёрнутой строки и сравним хеш подстроки с хешом соответствующего куска.

Соответствие границ: подстрока $[l, r)$ в исходной строке — это $[n - r,\, n - l)$ в перевёрнутой.

bool isPalindrome(int l, int r) {
    return forward.get(l, r) == backward.get(n - r, n - l);
}

Пересчёт границ — единственное место, где здесь ошибаются. Проверьте на строке из двух разных символов: там ошибка видна сразу.

Дальше, добавив бинарный поиск, получаем длину наибольшего палиндрома с центром в данной точке — то же, что даёт алгоритм Манакера, но без него. Медленнее на логарифм, зато не надо помнить Манакера.