[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 
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>l1>>r1>>l2>>r2;
        if(get(l1,r1) == get(l2,r2))
        cout