继续学习字符串匹配，fighting!!
题目地址：
http://poj.org/problem?id=1200
1 #include<cstdio>
2 #include<cstring>
3 #define N 10000000
4 char str1[N];
5 char str[N];
6 bool vis[N];
7 long long Rabin_Karp(int m,int p,int d)
8 {
9 int n=p;
10 long long t=0;
11 memset(vis,0,sizeof(vis));
12 int cnt=0;
13 long long h=1;
14 int tm=m-1;
15 long long tmp=d;
16 while(tm>0)
17 {
18 if(tm&1)
19 h=h*tmp;
20 tmp=tmp*tmp;
21 tm>>=1;
22 }//printf("h**%lld\n",h);
23 for(int i=0; i<m; ++i)
24 t=(d*t+(str[str1[i]]));//printf("%d // ",t);
25 vis[t]=true;cnt++;//printf("%d ",t[0]);
26 for(int i=1; i<=n-m; ++i)
27 {
28 t=((d*(t-str[str1[i-1]]*h))+(str[str1[i+m-1]]));//printf("%d // ",t);
29 if(!vis[t])
30 {vis[t]=true;cnt++;}
31 }//printf("**%d\n",cnt );
32 return cnt;
33 }
34 int main()
35 {
36 int n,nc;
37 // while(scanf("%d%d",&n,&nc)!=EOF)
38 // {
39 scanf("%d%d",&n,&nc);
40 scanf("%s",str1);
41 int len=strlen(str1);
42 memset(str,0,sizeof(str));
43 int count=1;
44 for(int i=0;i<len;++i)if(!str[str1[i]])str[str1[i]]=count++;
45 long long ans=Rabin_Karp(n,len,nc);
46 printf("%lld\n",ans);
47 // }
48 return 0;
49 }
posted on 2011-08-26 15:59
ACSeed 阅读(174)
评论(0) 编辑 收藏 引用