字符串hash中的karp-rabin算法的应用。
把字符串转换为进制数。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int hash[16000005];
char st[16000005];
int main()
{int n,nc;while(~scanf("%d %d %s",&n,&nc,st)){int num;num=0;mem(hash,0);int len=strlen(st);int ns;ns=nc;int i;int t=0;int name[10000];for (i =0; i < len; i++)if (name[st[i]] ==0)name[st[i]] = t++;for(i=0;i<n-1;i++){num=num*nc+name[st[i]];ns=ns*nc;}int ans=0;for(i=n-1;i<len;i++){num=(num*nc+name[st[i]])%ns;if(!hash[num])ans++;hash[num]=1;}printf("%d\n",ans);}return 0;
}