poj1200 hash

hash 其实一直想学的，但是一个是一直在刷 dp ，一个是各种要掌握的算法也很多，（别找理由了就是你懒……），总之在又一次 bc 出现hash但是我却茫然的时候，即使这道题不是简单 hash 就能做出来的，我也觉得真的一定要补一下这个算法了。

从鹏神的博客分类里面找了一道 hash 表的题目学习了一下然后做了一下

poj 1200：

题意：给定一个字符串，以及该字符串里字符的种类数 NC ，欲求规定长度为 N 的子串的种类数。

如果不知道 hash 这个算法，估计就是想个什么字符匹配的做法，可能也能做，但我估计超时的可能性也非常大，字典树貌似会但是我估计码起来应该也不简单，但既然这个是道 hash 做法，就往刚看的 hash 上靠，于是这个题目就出来了，其实 hash 表就是将一个串（或数组）的规定长度的子串（数组）看做一个 b 进制数（hash 值），不同子串的 hash 值相等的概率比较小，所以基本可以计算有多少个 hash 值就可以了。

而计算 hash 值的时候一般都是滚动优化，就是以上一个 hash 值减去少掉的一个元素再加上一个新的元素作为下一个 hash 值。本题中我取 b 为 NC，一般可以取

b 为 100000007，而本应计算完 hash 后 mod h，此时可以将所有数定为 ull 型，则 hash 值自然溢出可以不 mod ，或 b 取题目中某个数，在 hash 值比较小的时候一般也可以不用 mod 。

我基本也是只粗略学习了一下 hash ，翔神告诉我 hash 一般用于字符串或者数组的判重。

顺便把这个被我DEBUG成狗屎一样的代码贴上来，WA了无数次的原因其实是```昂， c 数组初值为 0 ，而我给字母赋值时也用到了 0 ，于是``` NC 进制数就变成了 NC + 1 进制数Orz

 1 #include<stdio.h>
 2 #include<string.h>
 3 /*
 4 #define ll long long
 5 #define ull unsigned long long
 6 */
 7 bool hash[16000005];
 8 int c[128];
 9 char s[16000005];
10 
11 int main(){
12     int N,nC;
13     while(scanf("%d%d",&N,&nC)!=EOF){
14         memset(c,-1,sizeof(c));
15         memset(hash,0,sizeof(hash));
16         scanf("%s",s);
17         unsigned long long t=0,tmp=1,NC = nC;
18         int ans=0;
19         int l=strlen(s),i,m=0,j;
20     //    printf("%c
",s[0]);
21         for(i=0;i<l;i++){
22         //    printf("AAA
");
23             if(c[s[i]]==-1){
24                 c[s[i]]=m;
25                 m++;
26             }
27             if(i==N-1){
28                 for(j=0;j<=N-1;j++){
29                     t+=c[s[j]]*tmp;
30                     tmp*=NC;
31                 }
32                 hash[t]=1;
33                 ans++;
34                 tmp/=NC;
35         /*        int a;
36                 a=t;
37                 printf("%lld
",t);
38                 while(a){
39                     printf("%lld",a%NC);
40                     a/=NC;
41                 }
42                 printf("
");*/
43             }
44             
45         //    printf("
tmp=%lld
",tmp);
46             else if(i>N-1){
47                 t/=NC;
48             /*    int a=t;
49                 while(a){
50                     printf("%lld",a%NC);
51                     a/=NC;
52                 }
53                 printf("
");*/
54             //    t-=c[s[i-N]]*tmp;
55                 t+=c[s[i]]*tmp;
56                 if(!hash[t]){
57                     hash[t]=1;
58                     ans++;
59                 }    
60             /*    
61                 a=t;
62                 printf("
");
63                 printf("%lld
",t);
64                 while(a){
65                     printf("%lld",a%NC);
66                     a/=NC;
67                 }
68                 printf("
");
69 */
70             }
71         }//    printf("
tmp=%lld
",tmp);
72     //    printf("
");
73     /*    for(i=0;i<=100000;i++){
74             if(hash[i]){
75                 t=i;
76                 while(t){
77                     printf("%lld",t%NC);
78                     t/=NC;
79                 }
80                 printf("
");
81             }
82         }
83 
84         printf("
");
85         
86         for(i=1;i<=127;i++){
87             if(c[i]>=0){
88                 
89                 printf("%2c%2d",char(i),c[i]);
90             }
91         }
92     
93         printf("
");*/
94         printf("%d
",ans);
95     
96     }
97 
98     return 0;
99 }

View Code