hdu 4821 String hash乱搞

String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if
(i) It is of length M*L;
(ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.

Two substrings of S are considered as “different” if they are cut from different part of S. For example, string “aa” has 3 different substrings “aa”, “a” and “a”.

Your task is to calculate the number of different “recoverable” substrings of S.

Input

The input contains multiple test cases, proceeding to the End of File.

The first line of each test case has two space-separated integers M and L.

The second ine of each test case has a string S, which consists of only lowercase letters.

The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.

Output

For each test case, output the answer in a single line.

Sample Input

3 3
abcabcbcaabc

Sample Output

2

Source

2013 Asia Regional Changchun

纯粹是寻找一个最佳的hash姿势？而且还要懂得合适的时间优化？
真的TLE了好几次，现场赛的难点
枚举字串起点不必从头找到尾，因为向后滚的操作涵盖了i>=l以后的字串

#include<cstdio>
#include<cstring>
#include<memory.h>
#include<string>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1e5+10;
const ULL base=29;//prime

map<ULL,int> mp;

ULL nbase[maxn],ha[maxn];
char str[maxn];
//string s;

void init()
{
    nbase[0]=1;
    for(int i=1;i<maxn;i++) nbase[i]=nbase[i-1]*base;
}

inline ULL Hash(char *s,int len,ULL *_hash)  //按各个后缀hash
{
    _hash[len]=0;
    for(int i=len-1;i>=0;i--)
        _hash[i]=_hash[i+1]*base+s[i]-'a';
}

inline ULL Get(ULL *_hash,int pos,int len)
{
    return _hash[pos]-_hash[pos+len]*nbase[len];
}

int main()
{
    init();
    int m,l;

    while(~scanf("%d%d",&m,&l))
    {
        LL ans=0;
        scanf("%s",str);
        int len=strlen(str);
        Hash(str,len,ha);
        for(int i=0;i<=len-m*l&&i<l;i++) //此处不加条件i<l就TLE
        {
            mp.clear();
            for(int j=i;j<i+m*l;j+=l)
            {
                ULL h=Get(ha,j,l);
                //cout<<h<<':'<<s.substr(j,l)<<endl;
                mp[h]++;
            }
            if (mp.size()==m) ans++;
            for(int j=i+m*l;j<=len-l;j+=l)
            {
                ULL h=Get(ha,j-m*l,l);
                //cout<<h<<':'<<s.substr(j-m*l,l)<<endl;
                mp[h]--;
                if (!mp[h]) mp.erase(h);
                h=Get(ha,j,l);
                //cout<<h<<':'<<s.substr(j,l)<<endl;
                mp[h]++;
                if (mp.size()==m) ans++;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}