poj 1200 Crazy Search (字符串哈希)
题意：一个字符串，其仅由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];
1int n,nc,i,j,sum,seed=0,ans=0;
2int main()
3{
4 // freopen("code/in.txt","r",stdin);
5 memset(Hash,false,sizeof(Hash));
6 memset(m,0,sizeof(m));
7 memset(str,'\0',sizeof(str));
8 cin>>n>>nc>>str;
9 int len = strlen(str);
10 for(int i = 0 ; i < len; ++i)
11 {
12 if(!m[str[i]]) //将每个字符赋值为相应进制的数
13 m[str[i]]=++seed;
14 if(seed == nc)
15 break;
16 }
17 for(i=0;i<=len-n;++i)
18 {
19 sum=0;
20 for(j=0;j<n;++j) //将字符串str[i],..,str[i+n-1]变为一个nc进制的整数,来判断是否重复出现过
21 sum=sum*nc+m[str[i+j]]-1;
1 if(!Hash[sum])
2 {
3 Hash[sum]=true;
4 ++ans;
5 }
6 }
7 cout<<ans<<endl;
8 return 0;
9}