回文Hash

转自 http://www.cnblogs.com/Lyush/archive/2012/12/10/2812096.html

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#define T 31LLU
using namespace std;
typedef unsigned long long Int64;

// 给定一个字符串，现在在这个串上进行一系列的动态操作
// 难点是在这些动态的修改的过程中，问任意一段是否为回文串 
// 思路是以某种方法来判定一个串是否相等，我们很容易想到字
// 符串的hash处理，对就是插值取模，解决了字符串比较的问题
// 选择插值取模的方法是有一定理由的，这个方法能够避免冲突
// 而且能够承受动态修改带来的hash值的更改 

char s[1000005];

int Q, N;

Int64 bit[1000005], f[1000005], t[1000005];

void pre() {
    bit[0] = 1;
    for (int i = 1; i <= 1000000; ++i) {
        bit[i] = bit[i-1] * T; 
    } // 先预处理所有的T的幂, ull拥有对上界自动取模的作用
}
/*
    树状数组保留的是最原始的值 
*/

inline int lowbit(int x) {
    return x & -x;
}

void add(int x, Int64 c[], Int64 val) {
    for (int i = x; i <= N; i += lowbit(i)) {
        c[i] += val;
    }
}

Int64 sum(int x, Int64 c[]) {
    Int64 ret = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ret += c[i];
    }
    return ret;
}

bool judge(int a, int b) { //(a,b) (N+1-b,N+1-a)   a-1, N-b
    // 这里有一个对阶的任务要完成，首先我们要找到这个阶数
    int x = a-1, y = N-b, z; // 最左边的阶码
    z = max(x, y); // z是我们要对齐的阶码
    Int64 ll = sum(b, f) - sum(a-1, f); // 从左往右看这个串
    Int64 rr = sum(N-a+1, t) - sum(N-b, t);
    ll *= bit[z-x];
    rr *= bit[z-y];
    return ll == rr;
}

void modify(int x, int val) {
    add(x, f, (val-s[x])*bit[x-1]);
    add(N+1-x, t, (val-s[x])*bit[N-x]);
    s[x] = val;
}

int main() {
    char op[5], ch[5];
    int a, b;
    pre();
    while (scanf("%s", s+1) == 1) {
        N = strlen(s+1);
        memset(f, 0, sizeof (long long) * (N+1));
        memset(t, 0, sizeof (long long) * (N+1));
        // 避免每次都对整个数组进行初始化
        for (int i = 1, j = N; i <= N; ++i, --j) {
            s[i] -= 'a';
            add(i, f, s[i]*bit[i-1]);
            add(j, t, s[i]*bit[j-1]);
            // 取的位置一样但是权值不一样
        }
        scanf("%d", &Q);
        while (Q--) { // 接受Q个擦操作
            scanf("%s", op);
            if (op[0] == 'Q') { // 询问的是[a ,b]是否是一个回文串
                scanf("%d %d", &a, &b);
                printf(judge(a, b)? "yes\n" : "no\n");
            } else {
                scanf("%d %s", &a, ch);
                modify(a, ch[0]-'a');
            }
        }
    }
    return 0;
}