首页 > 代码库 > 【kmp算法】【Rabin-Karp算法】[BeiJing2011]矩阵模板
【kmp算法】【Rabin-Karp算法】[BeiJing2011]矩阵模板
算法就不说了，反正是基于字符串匹配的。这里比较一下kmp和Rabin-Karp算法。
<法一>kmp算法。
| 592788 | lizitong | 2462 | Accepted | 4828 kb | 680 ms | C++/Edit | 2349 B | 2014-03-29 19:07:02 |
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m,a,b,q;char map[1001][1001],s[11][101][1001];int next[500001],pos[1001];void GetFail(char P[],int next[]){ next[0]=next[1]=0; for(int i=1;i<m;i++) { int j=next[i]; while(j&&P[i]!=P[j]) j=next[j]; if(P[i]==P[j]) next[i+1]=j+1; else next[i+1]=0; }}int find(char T[],char P[],int next[]){ n=strlen(T); m=strlen(P); GetFail(P,next); int j=0; for(int i=0;i<n;i++) { while(j&&P[j]!=T[i]) j=next[j];//如果j变成0仍不能满足P[j]==T[i]，则只增加i直到出现P[j]==T[i]为止。 if(P[j]==T[i]) j++; if(j==m) return i-m+1; } return -1;}int main(){ scanf("%d%d%d%d",&n,&m,&a,&b); for(int i=0;i<n;i++) scanf("%s",map[i]); scanf("%d",&q); for(int i=1;i<=q;i++) for(int j=0;j<a;j++) scanf("%s",s[i][j]); if(a==1) { for(int i=1;i<=q;i++) { bool flag=false; for(int j=0;j<n;j++) if(find(map[j],s[i][0],next)!=-1) { flag=true; printf("1\n"); break; } if(!flag) printf("0\n"); } return 0; } for(int i=1;i<=q;i++) { bool goal=false; for(int j=0;j<=n-a;j++) { bool flag=true; int Max=0; while(flag&&!goal) { for(int k=0;k<a;k++) { pos[k]=find(map[k+j]+Max,s[i][k],next); if(pos[k]==-1) { flag=false; break; } } if(!flag) break; Max=0; int count=0; for(int k=0;k<a;k++) { if(pos[k]==pos[0]) count++; Max=max(Max,pos[k]); } if(count==a) { goal=true; printf("1\n"); } } if(goal) break; } if(!goal) printf("0\n"); } return 0;}<法二>Rabin-Karp算法。
| 820112 | lizitong | 2462 | Accepted | 2880 kb | 980 ms | C++/Edit | 3103 B | 2014-12-27 11:35:21 |
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef unsigned long long ull;const ull seed=31;ull seeds[1001];int n,m,a,b,q,pos[1001];char map[1001][1001],s[11][101][1001];//暴力字符串比较bool Strcmp(const char a[],const int &L1,const int &R1,const char b[],const int &L2,const int &R2){ for(int i=L1,j=L2;i<R1;++i,++j) if(a[i]!=b[j]) return 0; return 1;}//自然上溢,L首指针,R尾指针,左闭右开ull BKDRhash(const char str[],const int &L,const int &R){ ull res=0; for(int i=L;i<R;++i) res=res*seed+str[i]; return res;}//预处理,便于hash(s[i...i+m-1]和hash(s[i+1...i+m]之间的转移) void init_seeds(){ seeds[0]=1; for(int i=1;i<1001;++i) seeds[i]=seeds[i-1]*seed;}//文本串查找,s文本串,sub子串int RabinKarp(const char s[],const char sub[]){ int n=strlen(s),m=strlen(sub); ull hsub=BKDRhash(sub,0,m),hs=BKDRhash(s,0,m); for(int i=0;i<=n-m;++i) { if(hs==hsub && Strcmp(s,i,i+m,sub,0,m)) return i; hs=(hs-s[i]*seeds[m-1])*seed+s[i+m];//O(1)转移 } return -1;}int main(){ init_seeds(); scanf("%d%d%d%d",&n,&m,&a,&b); for(int i=0;i<n;i++) scanf("%s",map[i]); scanf("%d",&q); for(int i=1;i<=q;i++) for(int j=0;j<a;j++) scanf("%s",s[i][j]); if(a==1) { for(int i=1;i<=q;i++) { bool flag=false; for(int j=0;j<n;j++) if(RabinKarp(map[j],s[i][0])!=-1) { flag=true; printf("1\n"); break; } if(!flag) printf("0\n"); } return 0; } for(int i=1;i<=q;i++) { bool goal=false; for(int j=0;j<=n-a;j++) { bool flag=true; int Max=0; while(flag&&!goal) { for(int k=0;k<a;k++) { pos[k]=RabinKarp(map[k+j]+Max,s[i][k]); if(pos[k]==-1) { flag=false; break; } } if(!flag) break; Max=0; int count=0; for(int k=0;k<a;k++) { if(pos[k]==pos[0]) count++; Max=max(Max,pos[k]); } if(count==a) { goal=true; printf("1\n"); } } if(goal) break; } if(!goal) printf("0\n"); } return 0;}虽然渐进复杂度相同，但是显然kmp更为稳定。
【kmp算法】【Rabin-Karp算法】[BeiJing2011]矩阵模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。