[Acwing] 字符串哈希 模板

前言

很模板的一道题
传送门 :

思路

将字符串转换为 p p p进制数,同时记录他们之间的 次方

然后需要查询一段字符串的时候直接
h [ r ] − h [ l − 1 ] ∗ p [ r − l + 1 ] ; h[r] - h[l-1]*p[r-l+1]; h[r]−h[l−1]∗p[r−l+1]; 即可

CODE

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned
#define ll long long
#define endl '\n'

const int N  = 1e5+10 , P= 131;
char str[N];
ull h[N],p[N];
ull get(int l,int r)
{
    return h[r] - h[l-1]*p[r-l+1];
}


void solve()
{
    int n,m;cin>>n>>m;
    cin>>(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;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1) == get(l2,r2))
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
    }
}
signed main()
//int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}
上一篇:AcWing 3208. Z字形扫描(模拟)


下一篇:AcWing 338. 计数问题