当前位置:网站首页>841. 字符串哈希

841. 字符串哈希

2022-07-07 17:36:00 Hunter_Kevin

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

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

输入格式
第一行包含整数 n 和 m,表示字符串长度和询问次数。

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

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

注意,字符串的位置从 1 开始编号。

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

每个结果占一行。

数据范围
1≤n,m≤105
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes

思路:
①、字符串下标从1开始
②、首先,将给定字符串,按下标从左往右求以i为末尾的字串,求出其基于字符的ascii码,基于P进制累加出来的字符串的hash值
③、根据经验值,字符串的hash值 ,以264的数据大小进行存储,以131或者13331为进制数的时候,累加的hash值对264取模,出现冲突的概率极小,认为忽略不计
④、unsigned long long 刚好是264,用ull存储的话,如果数据溢出,即高位截断,保留低位,相当于自动 对 264取模
⑤、算法的关键点是字符串前缀的hash值预处理 和 p^i数组的预处理
某个字串l~r对应的hash值,只需要 h[r] - h[l-1] * p[(r-1) - (l-1-1)] h[r] - h[l-1] * p[r-l+1]
例子:123456
求34的hash值
1234 - 12 * 10^2 == 34

#include <iostream>
#include <cstring>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;
//经验值 使用131或者13331 使用2^64的大小来存储字符串的hash值,理论上 以131或者13331为进制数求出来的字符串的hash值 mod 2^64 之后出现冲突的概率极小,可以看成不存在冲突

ULL h[N], p[N];//h数组存储下标前的字符串的hash值,p数组存储下标位置进制的位权值
char s[N];

int main()
{
    
    int n, m;
    cin>> n >> m >> s+1;

    //求字符串的hash值预处理结果 和 下标为i的位置对应的p^i
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
    
        p[i] = p[i-1] * P;//求出下标为i需要×的位权值 p^0 p^1 p^2 p^3 1 1*p 1*p*p 1*p*p*p
        h[i] = h[i-1] * P + s[i];//求出i位置对应的hash值,ULL溢出后,高位截断,保留低位,相当于对2^64取模,s[i]实际上的值为字符的哈希值
    }

    int l1,r1,l2,r2;
    while(m -- )
    {
    
        cin>>l1>>r1>>l2>>r2;
        ULL x = h[r1] - h[l1-1] * p[r1-l1+1];  //求某个字串的hash值,r1对应的哈希值 - (l1-1)对应的哈希值 * p^(r1-l1+1) 即 两个位置相差的p^(r1-1 - (l1-1-1))
        ULL y = h[r2] - h[l2-1] * p[r2-l2+1];
        if(x == y)cout<<"Yes"<<endl;        //如果两个字串的哈希值相等,则说明字符串相等
        else cout<<"No"<<endl;
    }

    return 0;
}
原网站

版权声明
本文为[Hunter_Kevin]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Hunter_Kevin/article/details/125662077