hdu 4821 字符串hash+map判重 String (长春市赛区I题)

http://acm.hdu.edu.cn/showproblem.php?pid=4821

昨晚卡了非常久，開始TLE，然后优化了之后，由于几个地方变量写混。一直狂WA。搞得我昨晚都失眠了，，。

这几次hash军写错的变量--tmp=(j==m-1)?ah[j]:(ah[j]-ah[j-m]*base[m]);  外层循环变量是i，我写的字符串hash的几题都写成tmp=(i==0)?

ah[j]:(ah[j]-ah[j-m]*base[m]); 二逼啊

题目大意：

给定一个字符串（最长10^5）。

从中选一个长度为 m * l 的子串。要求该子串能拆分为m个长度为 l 的一一不同的串(串仅仅要有一个字母不同即觉得是不同)。

问有多少种取法。

优化的方法--从字符串第一个位置開始，每L个的hash都算出来，当到了第一个第m个L位置的时候。继续往后算--去掉第一个L的hash值，加上第m*l+m的hash值

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdin)

const ull B = 1e8+7;

const int MAXN = 100010;

ull ah[MAXN],base[MAXN];

char a[MAXN];

int n;//length of a

int main()

{

   //IN("hdu4821.txt");

    int m,ll;

    int ans=0,cnt,last,sc;

    base[0]=1;

    ull tmp;

    rep(i,1,MAXN)

        base[i]=base[i-1]*B;

    while(~scanf("%d%d",&ll,&m))

    {

        scanf("%s",a);

        n=strlen(a);

        ah[0]=a[0];ans=0;

        for(int i=1;i<=n;i++)

            ah[i]=ah[i-1]*B+a[i]; //ah[i] 以i结尾的字符串的hash值

        for(int i=0;i<m && i+ll*m<=n;i++)

        {

            map<ull,int>mp;

            for(int j=i+m-1;j<i+ll*m;j+=m)

            {

                tmp=(j==m-1)?

ah[j]:(ah[j]-ah[j-m]*base[m]);

                mp[tmp]++;

            }

            if(mp.size()==ll)ans++;

            int pos=i+m-1;

            tmp=(i==0)?

ah[m-1]:(ah[pos]-ah[pos-m]*base[m]);

            mp[tmp]--;

            if(mp[tmp] == 0)mp.erase(tmp);

            for(int j=i+ll*m+m-1;j<n;j+=m)

            {

                tmp=ah[j]-ah[j-m]*base[m];

                mp[tmp]++;

                if(mp.size()==ll)ans++;

                pos+=m;

                tmp=ah[pos]-ah[pos-m]*base[m];

                mp[tmp]--;

                if(mp[tmp] == 0)mp.erase(tmp);

            }

            mp.clear();

        }

        printf("%d\n",ans);

    }

    return 0;

}