#include<stdio.h>
#include<vector>
#include<map>
#include<vector>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>

using namespace std;

const int mod=10000007;
int hash[mod];
int t[200];
char s[3000000];
bool cmp(int i,int j,int n){
    for(int p=0;p<n;p++)
        if(s[i+p]!=s[j+p])return 0;
    return 1;
}

int main(){
    int n,nc;
    while(~scanf("%d%d",&n,&nc)){
        memset(t,0,sizeof(t));
        int len=0,j=0;
        scanf("%s",s);
        for(;s[len];len++){
            if(!t[s[len]]){
                t[s[len]]=++j;
            }
        }
        memset(hash,-1,sizeof(hash));
        int res=0;
        int ans=0;
        for(int i=0;i<n;i++)
            res=(res*nc+t[s[i]])%mod;
        ans++;
        hash[res]=0;
        for(int i=1;i+n<=len;i++){
            res=0;
            for(int j=i;j<i+n;j++)
                res=(res*nc+t[s[j]])%mod;
            while(hash[res]!=-1&&!cmp(hash[res],i,n))
                res=(res+1)%mod;
            if(hash[res]==-1){
                hash[res]=i;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
}

• 代码有错 (22) mrsimon 2013-12-21 00:36:44
• Re:贴个自己写的hash代码 （200ms多） (6) zhanglistar 2014-10-13 22:30:32