Проверка на палиндромность

Информатика
1

как проверять на палиндромность подстроки за O(1) используя хэши?

2

Можно использовать хэш реверснутой строки и сравнивать соответствующие отрезки, то есть если надо проверить подстроку [l, r], мы ее сравним с подстрокой [n-r+1, n-l+1] в реверснутой строке

5 лайков
3

Тип делаю один хэш на обычной строке и 1 хэш на реверснутой?

1 лайк
4

да, так и делаешь

2 лайка
5

СПБГУ Тренировки be like:

2 лайка
6

там же еще есть проверка на четность и нечетность палиндрома?

7

не совсем понял вопрос, в данном случае происходит обычное сравнение s == reverse(s) только да О(1)

8

Я вот так проверяю:

bool H(int l, int r){
    if(h[r] - h[l - 1] * p[r - l + 1] == a[n - l + 1] - a[n - r] * p[r - l + 1])return 1;
    return 0;
}

h - хэш обычной строки
a - хэш реверснутой строки
p - степени числа 31
Но оно не работает

3 лайка
10

Возможно ты неправильно составляешь обратный хэш, т.к. в моей реализации твоя функция работает(2^64 mod):

for(int i = 1; i <= n; i++){
	h[i] = h[i - 1] * P + s[i];
	a[i] = a[i - 1] * P + s[n - i + 1]; 
}
11

тут может быть такое, что h[r] < h[l - 1] * p[r - l + 1], так как операции с модулем и тогда твой код неправильно проверит и из за этого нужно писать (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod

6 лайков