字符串hash

#include<iostream>
#include<string>
#include<map>
using namespace std;

typedef unsigned long long ull;

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

ull h[N],p[N];//注意ull,这样就不要有模数了 
string str;
void init()
{
    p[0]=1,h[0]=0;
    for(int i=1,j=str.size();i<j;i++)//下标从1开始，不是0 
    {
        h[i]=h[i-1]*P+str[i];//str字符串 
        p[i]=p[i-1]*P;//进制初始化 
    }
}

ull get(int l,int r)//得到某一区间的字符串哈希值 
{
    return h[r]-h[l-1]*(r-l+1);
}

bool check(int l1,int r1,int l2,int r1)
{
    return get(l1,r1)==get(l2,r2);
}