hdu 4821 String(字符串hash)

题目链接：hdu 4821 String

题意：

给你一个字符串，问你有多少子串，满足长度为m*len,并且这个子串能分成m个len长度的不同串。

题解：

BKDRhash+map来判重。注意的是要以len长分类来扫，这样才不会超时。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef unsigned long long ull;
const int str_len=1e5+7;
struct string_hash
{
    const static int seed=31;
    int len;
    ull h[str_len],b[str_len];
    inline int idx(char x)
    {
        return x-'a'+1;
    }
    void init()
    {
        h[0]=0,b[0]=1;
        F(i,1,str_len-1)b[i]=b[i-1]*seed;
    }
    void ins(char *s)//从1开始。
    {
        len=strlen(s+1);
        F(i,1,len)h[i]=h[i-1]*seed+idx(s[i]);
    }
    inline ull ask(int l,int r){return h[r]-b[r-l+1]*h[l-1];}//区间段hash值
}str;

int m,l,ans;
char s[str_len];
map<ull,int>cnt;
int main()
{
    str.init();
    while(~scanf("%d%d",&m,&l))
    {
        scanf("%s",s+1);
        str.ins(s),ans=0;
        for(int i=1;i<=l&&i+m*l<=str.len;i++)
        {
            cnt.clear();
            for(int j=i;j<i+m*l;j+=l)cnt[str.ask(j,j+l-1)]++;
            ans+=(cnt.size()==m);
            for(int j=i+m*l;j+l-1<=str.len;j+=l)
            {
                cnt[str.ask(j,j+l-1)]++;
                ull tmp;
                cnt[tmp=str.ask(j-m*l,j-m*l+l-1)]--;
                if(cnt[tmp]==0)cnt.erase(tmp);
                ans+=(cnt.size()==m);
            }
        }
        printf("%d
",ans);
    }
    return 0;
}