模板 KMP

2019-04-13 13:44发布

站内文章 / 模拟电子
12971 0 1722

KMP算法     是由Knuth，Morris，Pratt（简称KMP）共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。

 

字符串匹配问题

目标串S(长度为n的串)： abkabefkabkababca 模式串P(长度为m的串)： abkababca                                                      我们现在要查找模式串是否是目标串的子串，输出所有匹配位置。     字符串匹配问题-朴素算法    遍历 S 的每个字符，以该字符为始与 P 比较，全部匹配就输出；否则直到 S 结束。代码如下   string S,P; cin>>S>>P; int n=S.size(),m=P.size(); for(int k=0;k<=n-m;k++) //枚举S串开始位置 { int i=k,j=0; //i为S的指针，j为P的指针 while(j 算法时间复杂度：O(n*m)，n和m表示字符串长度     ——————————————————————我  是  分  割  线————————————————————————    

           KMP算法-算法流程

 
  KMP时间复杂度：O(m+n)       // O(m)  求 nxt[ i ]
具体去洛谷理解一下吧 #include #include #include #include #include #include using namespace std; string a,b; int nxt[1000005]={0}; int ans[1000005]={0},num=0; void nxtt(string s) { int len=s.size(); nxt[0]=nxt[1]=0; for(int i=1;i>a>>b; nxtt(b); kmp(a,b); for(int i=1;i<=num;i++) printf("%d ",ans[i]); for(int i=1;i<=b.size();i++) printf("%d ",nxt[i]); return 0; }  

热门文章