$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

注意：

1. 将字符串映射成 P 进制的哈希值
2. 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
3. 冲突问题：通过巧妙设置P (131 或 13331) , Q (2 ^ 64)的值，一般可以理解为不产生冲突
4. h[i] 表示 str[1~i],即 str 的前缀和数组

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n,m;
char str[N];
int p[N],h[N];

//获取[l,r]的字符串哈希值
ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}

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

    //预处理p数组和h数组
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];    
    }

    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        cout<<(get(l1,r1)==get(l2,r2)?"Yes":"No")<<endl;
    }

    return 0;
}