AcWing | 字符串前缀哈希

ゞ浴缸里的玫瑰 2022-12-20 05:45 195阅读 0赞

**题目内容**

> 给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断\[l1,r1\]和\[l2,r2\]这两个区间所包含的字符串子串是否完全相同。
> 
> 字符串中只包含大小写英文字母和数字。

**输入格式**

> 第一行包含整数n和m，表示字符串长度和询问次数。
> 
> 第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。
> 
> 接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。
> 
> 注意，字符串的位置从1开始编号。

**输出格式**

> 对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。
> 
> 每个结果占一行。

**数据范围**

> 1≤n,m≤ 1 0 5 10^5 105

**输入样例：**

8 3
    aabbaabb
    1 3 5 7
    1 3 6 8
    1 2 1 2

**输出样例：**

Yes
    No
    Yes

--------------------

**思路：**

*  字符串前缀哈希
 *  将字符串看成`p`进制的数，`h[i]`表示字符串前`i`个字符。
    
     *  例如：str=“ABCABCDEFG”；那么：  
        h\[0\]=0; h\[1\]="A"的哈希值；  
        h\[2\]=“AB”的哈希值…
     *  然后"ABCD"这个子串就相当于（1 2 3 4）的p进制表示：  
        ![在这里插入图片描述][20201111073951872.png_pic_center]
 *  其中需要注意的是：
    
     *  不能将某值映射成0
     *  不考虑冲突的存在，有研究表明当`p`取`131`或者`133331`，且`Q`取 2 64 2^\{64\} 264时几乎不会存在冲突。  
        ![在这里插入图片描述][20201111074246924.png_pic_center]
 *  至此，我们就可以用以上方法结合前缀哈希的方法算出任意子串的哈希值。
    
     *  比如，我们已知`h[R]`以及`h[L-1]`的哈希值，我们就可以算出`h[R]~h[L-1]`之间的哈希值。
     *  因为我们将字符串看成了p进制数，左边为高位，右边为低位，我们只要将h\[L-1\]x p R − L + 1 p^\{R-L+1\} pR−L\+1，我们就能将h\[R\]以及h\[L-1\]的最高位对其，再计算h\[R\]-h\[L-1\]x p R − L + 1 p^\{R-L+1\} pR−L\+1，就能得到区间的哈希值了。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]
 *  然后在取模时有一个小技巧，我们可以用`unsigned long long`来存储`h[i]`，这样当其溢出时，就相当于自动取模了。

**完整代码：**

#include<iostream>
    using namespace std;
    typedef unsigned long long ULL;//由于前缀值很大，所以要将数组中的数据定义位ULL型
    const int N=100010,P=131;//P为权重
                            //131为经验值 即P=131或13331时 哈希冲突的可能性最小
    
    int n,m;
    char str[N];
    ULL h[N]; //h[]存放字符串的前缀值
    ULL p[N];//p[]存放各个位数的相应权值
    ULL get(int l,int r){ 
        return h[r]-h[l-1]*p[r-l+1];//这步其实是将h[l-1]左移
        //其目的事实上是为了将h[l-1]的高位与h[r]相对齐从而才可以完成计算
    }
    int main(){ 
        scanf("%d%d%s",&n,&m,str+1);//str+1是为了从1开始存
        p[0]=1;//注意这步千万不要忘了 最开始的权值必须赋值为1 否则接下来就会出错
        for(int i=1;i<=n;i++){ //预处理
            p[i]=p[i-1]*P;//计算每个位上的相应权值
            h[i]=h[i-1]*P+str[i];//计算字符串前缀值
            //最新加入的数的权值为p的0次 所以直接加上str[i]即可
        }
        while(m--){ 
            int l1,r1,l2,r2;
            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            
            if(get(l1,r1)==get(l2,r2))puts("Yes");
            else puts("No");
            
        }
        return 0;
    }

[20201111073951872.png_pic_center]: /images/20221120/42dfd909b10442a0a0583faedaf31c9e.png
[20201111074246924.png_pic_center]: https://img-blog.csdnimg.cn/20201111074246924.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201111074617962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2,size_16,color_FFFFFF,t_70#pic_center