Как через хеши найти наибольший общий префикс двух суффиксов за O(log n) (бинпоиск по LCP)?
Без суффиксного массива хочу отвечать на запросы «LCP суффиксов, начинающихся в позициях i и j». Идея — бинпоиск по длине совпадения с проверкой через хеши. Но не уверен, как корректно ставить границы бинпоиска и почему получается O(log n).
2 ответа
Функция equal_len(i, j, len) = «совпадают ли s[i..i+len-1] и s[j..j+len-1]» проверяется за O(1) через префиксные хеши. LCP монотонна: если совпадают первые len, то совпадают и первые len-1. Значит бинпоиск по len корректен.
int lcp(int i, int j, int n, const Hashing& H) {
int lo = 0, hi = n - max(i, j); // нельзя выйти за конец строки
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (H.get(i, i + mid - 1) == H.get(j, j + mid - 1)) lo = mid;
else hi = mid - 1;
}
return lo;
}
Границы: верхняя hi = n - max(i,j) — дальше один из суффиксов кончится. Округление (lo+hi+1)/2 вверх — чтобы при lo=mid цикл не зациклился. Каждый запрос — O(log n) (логарифм проверок по O(1) каждая), препроцессинг хешей — O(n).
Это частая замена суффиксному массиву, когда лень его писать: сортировку суффиксов тоже можно сделать через такой lcp как компаратор, получив SA за O(n log^2 n).
Осторожно с краем: если внутри бинпоиска mid превысит остаток строки, H.get уйдёт за границу. Именно поэтому hi ограничен n - max(i,j) ИЗНАЧАЛЬНО, а не n. И помните про вероятностность: для абсолютной надёжности — 2^61-1 со случайной базой, иначе на анти-хеш тесте LCP может «совпасть» там, где строки различны, и вы получите WA.