题目链接：http://poj.org/problem?id=1200
题意：给定一个字符串，字符串只有NC个不同的字符，问这个字符串所有长度为N的子串有多少个不相同。
思路：字符串HASH，因为只有NC个不同的字符，所以我们可以把字符串看成是一个NC进制的串，然后计算出字符串的前缀HASH。然后枚举起点判断子串的HASH值是否已经存在。因为有了前缀HASH值，所以转移是O(1)的。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<set>
using namespace std;
typedef long long int LL;
typedef unsigned int uint;
const int MAXN=+;
const int mod=+;
int Hash[MAXN],vis[];
char str[MAXN];
bool cnt[MAXN];
int pow_mod(int a,int b){
int ans=;
while (b)
{
if (b & )
ans = (1LL*ans*a)%mod;
b >>= ;
a = (1LL*a*a)%mod;
}
return ans;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
int hashNum=,ans=;
scanf("%s",str+);
memset(vis,-,sizeof(vis));
memset(cnt,false,sizeof(cnt));
int len=strlen(str+);
for(int i=;i<=len;i++){
if(vis[str[i]]==-){
vis[str[i]]=hashNum;
Hash[i]=hashNum++;
}
else{
Hash[i]=vis[str[i]];
}
}
int P=pow_mod(m,n-),pNum=;
for(int i=;i<=len;i++){
if(i>=n){
pNum=(((pNum-Hash[i-n]*P)*m+Hash[i])%mod+mod)%mod;
if(!cnt[pNum]){
cnt[pNum]=true;
ans++;
}
}
else{
pNum=(pNum*m+Hash[i])%mod;
}
}
printf("%d\n",ans);
}
return ;
}