前言
暴力模式匹配算法的最坏时间复杂度为O(nm)，其中n和m分别为主串和模式串的长度。
改进的模式匹配算法——KMP算法
上图的匹配过程，在第三趟匹配中，i=7、j=5的字符比较不等，于是又从i=4、j=1重新开始比较。仔细观察会发现，i=4和j=1，i=5和j=1及i=6和j=1这三次比较都是不必进行的，因为从第三趟部分匹配的结果可知，主串中第4、5和6个字符是’b’、‘c’和’a’。因为模式中第一个字符是‘a’，因此它无需再和这三个字符进行比较。而仅需将模式向右滑动3个字符的位置而继续进行i=7、j=2时的字符比较 即可。
字符串的前缀后缀和部分匹配值
KMP算法的原理
对算法的改进方法：
已知：右移位数 = 已匹配的字符数 - 对应的部分匹配值
写成：Move=(j-1)-PM[j-1]
使用部分匹配值时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来有些不方便，所以将PM表右移一位，这样哪个元素匹配失败，直接看它部分匹配值即可。
将上例中字符串‘abcac’的PM表右移一位，就得到了next数组：
KMP算法进一步优化
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<math.h> #include<bitset> #include<limits.h> #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r>>1) #define over(i,s,t) for(register int i=s;i<=t;++i) #define lver(i,t,s) for(register int i=t;i>=s;--i) //#define int __int128 using namespace std; #undef mid typedef long long ll; typedef unsigned long long ull; //typedef pair<int,int> PII; const int N=1e6+7; const int mod=1e9+7; const ll INF=1e15+7; const double EPS=1e-10; const int p=131;//13331 int nex[N]; int n,m,len,cnt; int j; char a[N]; void calc_nex() { nex[1]=0; for(int i=2,j=0;i<=n;++i){ while(j>0&&a[i]!=a[j+1])j=nex[j]; if(a[i]==a[j+1])j++; nex[i]=j; } } int main() { while(scanf("%d",&n)!=EOF&&n){ scanf("%s\n",a+1); printf("Test case #%d\n",++cnt); calc_nex(); for(int i=2;i<=n;i++){ if(i%(i-nex[i])==0&&i/(i-nex[i])>1) printf("%d %d\n",i,i/(i-nex[i])); } puts(""); } return 0; }
下一章
树与二叉树
有帮助的话点赞 收藏加关注哦
