构造字符串的HASH表,O(1) 时间内对其子串进行判断是否相等
struct
{
ll M = 11411;
ull pre[N],id[N];
char s[N];
void init()
{
pre[0] = 1; M = 11411;//233
FOR(i,1,N-1)pre[i] = pre[i-1]* M;
FOR(i,1,n) id[i] = id[i-1] * M + (s[i] - 'a' +1);
}
ull gethash(ll l,ll r)
{
return id[r] - id[l-1] * pre[r-l+1];
}
}O_O;