POJ 1200Crazy Search解题报告

字符串哈希的入门题目，字符串哈希算法，大部分用的其实是进制表示，通过转换成不同进制的整数来表示一个字符串，因为计算机存储整数是有最大限度的，所以按照这种方法进行字符串哈希得到的整数有可能会越界，越界处理之后产生的结果，就是可能会造成冲突：两个字符串的值会相同，这道题不用考虑那么多，不过因为字符串太长，所以要对一个数取模，最多出现NC个不同的字符，可以像整数一样利用NC进制来表示，参照二进制的数值表示也能知道，要对NC^N取模

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define LEN 17000000
 6 bool val[LEN];
 7 char s[LEN];
 8 int use[300];
 9 int main()
10 {
11     int i,j,N,NC,len;
12     int mod;
13     while(scanf("%d%d",&N,&NC)!=EOF)
14     {
15         memset(val,0,sizeof(val));
16         memset(use,0,sizeof(use));
17         scanf("%s",s);
18         len = strlen(s);
19         int res = 0;
20         for(i = 0;i < len;i++)
21             use[s[i]] = 1;
22         j = 0;
23         for(i = 0;i < 300;i++)
24             if(use[i])
25                 use[i] = j++;
26         mod = 1;
27         for(i = 0;i < N-1;i++)
28             mod *= NC;
29         for(i = 0;i < N;i++)
30             res = res * NC + use[s[i]];
31         val[res] = true;
32         for(i = N;i < len;i++)
33         {
34             res = res % mod * NC + use[s[i]];
35             val[res] = true;
36         }
37         int count=0;
38         mod *= NC;
39         for(i = 0;i <= mod;i++)
40            if(val[i])       
41                count++;
42         printf("%d\n",count);
43     }
44     return 0;
45 }