Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：一个字符串，其仅由nc种字符组成，问其所有长度为n的字串里，共用多少种不同的。
思路：一开始木有懂nc种字符有什么用…
然后写了hash，发现会TLE。。。因为用到了map，被卡了个log..
nc的作用是，可以把字符串看成一个nc进制的数，这样做的好处是，得到的hash值可以尽可能的小而且保证了不同的字符串对应了不同的hash值。
然后就可以不用map而是一个数组，就变成了O(1)赋值和判断了。。。
（然而没有数据范围其实还是有点耍流氓的嫌疑。。
1#include <iostream>
2#include <cstring>
3#include <stdio.h>
4using namespace std;
5const int N=16000005; //题目给出子串的最大和不超过16M
6const int NUM=257;
7bool Hash[N];
8int m[NUM];
9char str[1000000];
10
11int n,nc,i,j,sum,seed=0,ans=0;
12int main()
13{
14 // freopen("code/in.txt","r",stdin);
15 memset(Hash,false,sizeof(Hash));
16 memset(m,0,sizeof(m));
17 memset(str,'\0',sizeof(str));
18 cin>>n>>nc>>str;
19 int len = strlen(str);
20 for(int i = 0 ; i < len; ++i)
21 {
22 if(!m[str[i]]) //将每个字符赋值为相应进制的数
23 m[str[i]]=++seed;
24 if(seed == nc)
25 break;
26 }
27 for(i=0;i<=len-n;++i)
28 {
29 sum=0;
30 for(j=0;j<n;++j) //将字符串str[i],..,str[i+n-1]变为一个nc进制的整数,来判断是否重复出现过
31 sum=sum*nc+m[str[i+j]]-1;
32
33 if(!Hash[sum])
34 {
35 Hash[sum]=true;
36 ++ans;
37 }
38 }
39 cout<<ans<<endl;
40 return 0;
41}