Как через хеши проверять, является ли подстрока палиндромом за O(1)?
Нужно много раз отвечать на запрос «является ли s[l..r] палиндромом». Хочу через хеши, но не понимаю, как получить хеш «развёрнутой» подстроки, чтобы сравнить с прямым. Манакер пока не осилил.
2 ответа
Идея: посчитать хеши для прямой строки и отдельно для перевёрнутой строки rev = reverse(s). Тогда «прямой хеш s[l..r]» сравниваем с «хешом того же отрезка, но в обратной строке». Палиндром ⟺ прямой хеш равен обратному.
Главное — аккуратно пересчитать индексы для rev. Если позиция в s это i, то в rev это n-1-i. Отрезок [l..r] в прямой соответствует отрезку [n-1-r .. n-1-l] в rev.
struct PalCheck {
Hashing fwd, bwd;
int n;
PalCheck(const string& s, uint64_t base)
: fwd(s, base), bwd(string(s.rbegin(), s.rend()), base), n(s.size()) {}
bool is_pal(int l, int r) {
uint64_t a = fwd.get(l, r);
uint64_t b = bwd.get(n - 1 - r, n - 1 - l);
return a == b;
}
};
Препроцессинг — O(n), каждый запрос — O(1). Для надёжности используйте 2^61-1 со случайной базой, иначе на палиндромных задачах любят подкладывать анти-хеш тесты.
Если задача — посчитать ВСЕ палиндромы или найти длиннейший, хеши с бинпоиском по радиусу дают O(n log n), а Манакер — O(n). Но для точечных запросов «палиндром ли отрезок» хеши проще и достаточно быстры. Выбор зависит от того, нужны ли вам именно центры палиндромов (тогда Манакер) или произвольные отрезки (тогда хеши).