poj1200Crazy Search (哈希)

 1 #include <iostream>
 2 #include <sstream>
 3 #include <ios>
 4 #include <iomanip>
 5 #include <functional>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <string>
 9 #include <list>
10 #include <queue>
11 #include <deque>
12 #include <stack>
13 #include <set>
14 #include <map>
15 #include <cstdio>
16 #include <cstdlib>
17 #include <cmath>
18 #include <cstring>
19 #include <climits>
20 #include <cctype>
21 using namespace std;
22 #define XINF INT_MAX
23 #define INF 0x3FFFFFFF
24 #define MP(X,Y) make_pair(X,Y)
25 #define PB(X) push_back(X)
26 #define REP(X,N) for(int X=0;X<N;X++)
27 #define REP2(X,L,R) for(int X=L;X<=R;X++)
28 #define DEP(X,R,L) for(int X=R;X>=L;X--)
29 #define CLR(A,X) memset(A,X,sizeof(A))
30 #define IT iterator
31 typedef long long ll;
32 typedef pair<int,int> PII;
33 typedef vector<PII> VII;
34 typedef vector<int> VI;
35 const int B=16000057;
36 char s[B];
37 bool a[B];
38 bool c[26];
39 map<char,int>m;
40 int main()
41 {
42     ios::sync_with_stdio(false);
43     int n,nc;
44     while(scanf("%d%d",&n,&nc)!=EOF){
45     scanf("%s",s);
46     int len=strlen(s);
47     int b=0;
48     memset(a,0,sizeof(a));
49     for(int i=0;i<len;i++)
50     {
51         if(c[s[i]-‘a‘]==0)c[s[i]-‘a‘]=1;
52     }
53     int t=0;
54     for(int i=0;i<26;i++)
55     {
56         if(c[i])
57         {
58             m[i+‘a‘]=t;
59             t++;
60         }
61     }
62     b=1;
63     int bl=0;
64     //for(int i=0;i<len;i++)cout<<m[s[i]]<<endl;
65     for(int i=0;i<n;i++)b=(b*nc)%B;
66     for(int i=0;i<n;i++)
67     {
68         bl=((bl*nc)%B+m[s[i]])%B;
69     }
70     a[bl]=1;
71     for(int i=n;i<len;i++)
72     {
73         bl=((bl*nc-m[s[i-n]]*b+B)%B+m[s[i]])%B;
74         a[bl]=1;
75     }
76     int ans=0;
77     for(int i=0;i<B;i++)
78     {
79         if(a[i])ans++;
80     }
81     printf("%d\n",ans);
82     }
83     return 0;
84 }