字母串哈希模板题题解：哈希+前缀和+进制转换+预处理指数函数-Toy模板网

这篇具有很好参考价值的文章主要介绍了字母串哈希模板题题解：哈希+前缀和+进制转换+预处理指数函数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、链接

841. 字符串哈希

二、题目

给定一个长度为 nn 的字符串，再给定 mm 个询问，每个询问包含四个整数 l1,r1,l2,r2l1,r1,l2,r2，请你判断 [l1,r1][l1,r1] 和 [l2,r2][l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 nn 和 mm，表示字符串长度和询问次数。

第二行包含一个长度为 nn 的字符串，字符串中只包含大小写英文字母和数字。

接下来 mm 行，每行包含四个整数 l1,r1,l2,r2l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 11 开始编号。

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

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

输出样例：

Yes
No
Yes

难度：简单

时/空限制：1s / 64MB

总通过数：51709

总尝试数：78284

来源：模板题

算法标签

三、题意

输入一个字符串，输入两个区间，判断这两个区间是否完全相等

四、代码

#include<iostream>

using namespace std;

typedef unsigned long long ULL;

const int N=1e5+10,P=131;

ULL h[N],p[N];
char str[N];

ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P;
    }
    
    while(m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1)==get(l2,r2))  printf("Yes\n");
        else    printf("No\n");
    }
    
    return 0;
}

五、总结

1.把字符串看成是数字，每一个字符看成是数位上的一个数字，把字符串子串看成是P进制的数字，先把P进制的数字转换成10进制的数字，然后对2^64取模，2^64是经验值，P=131也是经验值，如果数据超过unsigned long long相当于对2^64取模，所以定义为unsigned long long就不需要进行单独的取模运算。

2.typedef的使用，是把一个比较长的api 自定义一个比较简略的方式，比如这样：

typedef unsigned long long ULL;

3.考虑到前缀和类似思想，数组下标从1开始使用，前缀和：前缀和 795. 前缀和，还有另一方面的考虑，假设一个字符a是0，那么aa按照进制转换也是0，但是实际上a和aa从字符串上来讲是不一样的两个字符串，从数字的角度来说是相等的，但是按照题目要求是不相等的。

4.把字符串当作是P进制数来进行计算是这一行代码

h[i]=h[i-1]*P+str[i];

5.预处理指数函数，求出以P为底的指数函数的数值

p[i]=p[i-1]*P;

注意p[0]=1，需要进行初始化，不然无法进行上述计算

6.定义一个函数，输入两个区间端点，返回一个数值，比较这两个数值可以得出答案，这个函数的具体实现是：类似于前缀和的公式，

h[r]-h[l-1]*p[r-l+1];

可以理解为一个字符串，右边的是abcde,左边的是abc,现在两个字符串都被预处理成为十进制的数字了，需要把数字移到对齐，也就是用abc放在abcde正下方，列减法竖式的那种情况，P进制最右边是P^0，往左依次是p^1,p^2,p^3......到最左边是p^(r-1),h[l-1]的最左边是p^(l-1-1),把他们移动到同一位，相当于在h[l-1]后面加上零，使得两个字符串对齐，abcde-abc00，大概是这种感觉，(r-1)-(l-1-1)==r-l+1,从而可以推出上述式子，其实最好的方法是熟练应用这个公式

7.代码细节，输入从1开始计数的字符串