构造字符串的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;