String HDU

String

 HDU - 4821 

题意：求长串中存在多少个长度为M*L的子串（是由M个长度为L的子串构成的）

算是第一道哈希题了，看的别人的代码

先求出原串左边起到第i位的哈希值h[i]，然后枚举起点，计算出前M段，然后利用滑动窗口右移，因此起点只需从1枚举到L即可

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int maxn=100010;
const int seed=31;

char s[maxn];
int M,L;
ull h[maxn],base[maxn];
map<ull,int> mp;
ull _hash(int l,int r)  //求区间l到r的哈希值
{
    return  h[r]-h[l-1]*base[r-l+1];
}

int main()
{
    base[0]=1;
    for(int i=1;i<maxn;i++)
        base[i]=base[i-1]*seed;
    while(scanf("%d%d",&M,&L)!=EOF){
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            h[i]=h[i-1]*seed+s[i]-'a'; 
        int ans=0;
        for(int i=1;i<=L&&i+M*L<=len;i++){   
            mp.clear();
            for(int j=i;j<i+M*L;j+=L){
                ull x=_hash(j,j+L-1);
                mp[x]++;
            }
            if(mp.size()==M)ans++;
            //下面相当于为M段的滑动窗口，每次右移判断是否满足
            for(int j=i+M*L;j+L-1<=len;j+=L){
                ull x=_hash(j,j+L-1);
                mp[x]++;  //右边进来
                ull y=_hash(j-M*L,j-M*L+L-1);
                mp[y]--;   //左边出去
                if(mp[y]==0) mp.erase(y);
                if(mp.size()==M) ans++;
            }
        }
        printf("%d
",ans);
    }

}