字符串hash

String

3 3
abcabcbcaabc

2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

typedef unsigned long long int ull;

const int maxn=100100;

int L,M;
char str[maxn];

ull xp[maxn],hash[maxn];
map<ull,int> ck;

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

ull get_hash(int i,int L)
{
	return hash[i]-hash[i+L]*xp[L];
}

int main()
{
	init();
    while(scanf("%d%d",&M,&L)!=EOF)
    {
        scanf("%s",str);
        int n=strlen(str);
        hash[n]=0;
        for(int i=n-1;i>=0;i--)
        {
        	hash[i]=hash[i+1]*175+(str[i]-'a'+1);
        }
        int ans=0;
        for(int i=0;i<L;i++)
        {
        	ck.clear();
        	int duan=0;
        	for(int j=0;i+(j+1)*L-1<n;j++)
        	{
        		/// i+j*L <---> i+(j+1)*L-1
        		duan++;
        		ull hahashsh=get_hash(i+j*L,L);
        		ck[hahashsh]++;
        		if(duan>=M)
        		{
        			if(duan>M)
        			{
	        			/// M+1 ago  : i+(j+1)*L-L*(M+1)
	        			ull Mago=get_hash(i+(j+1)*L-L*(M+1),L);
	        			if(ck[Mago])
	        			{
	        				ck[Mago]--;
	        				if(ck[Mago]==0) ck.erase(Mago);
	        			}
        			}
        			if(ck.size()==M) ans++;
        		}
        	}
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDOJ 4821 String

原文：http://blog.csdn.net/ck_boss/article/details/38888341