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

Tabris

CSDNhrbust字符串

发布于：2017年5月9日

次浏览

[原创]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) = \sum_{i=1}^i (string[i]\times x^i)

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

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

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

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

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

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

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

# 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;
}

本页文档最后更新于：2021年5月16日

CSDN

hash

[原创]山东省第八届ACM大学生程序设计竞赛训练总结 [8/11] 待补

[原创]山东省第八届 ACM 大学生程序设计竞赛训练总结 [8/11] 待补 2017-05-11 21:10:00 Tabris_ 阅读数：635 博客爬取于 2020-06-14 22...

[原创]第十三届北京师范大学程序设计竞赛决赛【(6+2)/10】

[原创]第十三届北京师范大学程序设计竞赛决赛【(6+2)/10】 2017-05-09 11:30:44 Tabris_ 阅读数：1236 博客爬取于 2020-06-14 22:40:4...