[原创]hrbustoj 1681 回文串 [BIT]【字符串hash】

2017-05-09 14:02:21 Tabris_ 阅读数：566

博客爬取于2020-06-14 22:40:43
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/71453698

题目链接:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1681
————————————————————————————————————————————

回文串
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 121(25 users) Total Accepted: 30(12 users) Rating: Special Judge: No
Description
现在我们有一个很长很长的字符串，并且我们将有两种操作。
C i y:将第i个字符变成y
Q i j:检查第i个字符到第j个字符是否为一个回文串
Input
输入的第一行是一个整数T，表示一共有T组测试数据；
对于每组测试数据，第一行包含一个字符串长度不超过1000000。
接下来一行为一个整数N代表操作次数。N不超过1000000
接下来N行包含一种操作。
所有的字母都是小写字母。
Output
对于每种操作，如果相应的字符串为回文串输出"yes"，后则输出"no"。
Sample Input
1
aaaaa
4
Q 1 5
C 2 b
Q 1 5
Q 1 3
Sample Output
yes
no
yes

————————————————————————————————————————————

我们判定一个字符串是不是回文的只需判断正过来和倒过来是不是相等的就好了.

对于字符串是不是相等的 ，正常需要O(length)判定，对于本题，显然是不可取的。

所以介绍下字符串hash算法，

hash就是映射吧，将一个字符串集合中的每个映射为一个值，这些值互不相同

随意设一个常数x

string(1,i)=∑i=1i(string[i]×xi)string(1,i) = \sum_{i=1}^i (string[i]\times x^i)

这样就能将一个字符串映射为一个正整数,

虽然这样计算的结果很可能是相同的,但是可喜的是相同的概率十分小.所以可以直接使用.

但是一般我们采用的是unsigned long long int,在计算中也不需要取模操作,因为运算的自然溢出就相当于对264−12^64-1取模了。

这样下来,我们只需要将字符串正着hash一遍,倒着hash一遍,就可以了,

因为有修改操作，所以我们采用BIT维护下。

注意：判定两个子串的时候，x的指数不对应，只需要在小的那个结果乘上差的那部分xix^i就好了

附本题代码
————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# include <bits/stdc++.h>

using namespace std;
typedef long long int LL;
typedef unsigned long long int ULL;
const int N = 1e6+7;


ULL sum[N][2];int len ;
# define lowbit(x) (x&-x)
void update(int i,ULL v,int w){
    for(;i<=len;i+=lowbit(i)) sum[i][w]+=v;
}
void update2(int i,ULL v,int w){
    for(;i<=len;i+=lowbit(i)) sum[i][w]-=v;
}
ULL getSum(int i,int w){
    ULL res = 0;
    for(;i;i-=lowbit(i)) res+=sum[i][w];
    return res;
}

char a[N],b[10];
ULL h[N];
void init(){
    h[0]=1;
    for(int i=1;i<N;i++)h[i]=h[i-1]*29;
}
int main(){
    init();
    int _;
    scanf("%d",&_);
    while(_--){memset(sum,0,sizeof(sum));
        scanf("%s",a+1);
        len = strlen(a+1);
        for(int i=1;a[i];i++)
            update(i,h[i]*(a[i]-'a'+1),1),update(i,h[i]*(a[len-i+1]-'a'+1),0);
        int n,l,r;
        scanf("%d",&n);
        while(n--){
            scanf("%s",b);
            if(b[0]=='Q'){
                scanf("%d%d",&l,&r);
                ULL tem = getSum(r,1)-getSum(l,1);
                ULL tmp = getSum(len-l+1,0)-getSum(len-r+1,0);
                if(tem*h[len-r+1] == tmp*h[l]) puts("yes");
                else           puts("no");
            }
            else {
                scanf("%d%s",&l,b);
                update2(l,h[l]*(a[l]-'a'+1),1);
                update2(len-l+1,h[len-l+1]*(a[l]-'a'+1),0);
                a[l]=b[0];
                update(l,h[l]*(a[l]-'a'+1),1);
                update(len-l+1,h[len-l+1]*(a[l]-'a'+1),0);
            }
        }
    }
    return 0;
}