kmp算法详解
由于网上题解较多,而他们也讲的非常的好啊,我这里只是简单地再总结一下,以及一些我自己在学习时的感受
这里先附上我学习时所用的博客,表示我的感谢.
http://blog.csdn.net/yutianzuijin/article/details/11954939/
https://segmentfault.com/a/1190000007066358
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
———————————————————————————————————————
一.为什么要用kmp算法
我们在萌新阶段如果遇到字符串匹配的题目,想必都是最暴力的方法,一位一位的判断,时间复杂度为O(n*m),就像如下图
很显然我们可以发现第四次和第五次都只判断了第一位就失配了,很明显这两次是很多余的,
于是kmp算法就依据这个特点来执行
二.kmp算法中最重要的next数组
kmp算法作为一个效率很高的字符串匹配方法,next数组便是其中的核心
他记录的是在第i位时,前缀和后缀都相等时的最大长度
好吧这样说可能有点抽象,来举个栗子
| 字符串 | A | B | C | D | A | B | D |
| next数组 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
在第一位{A} 前缀{Ø} 后缀{Ø},next[1]=0; (Ø表示空集)
在第二位{AB} 前缀{A} 后缀{B},共同部分{Ø},next[2]=0;
在第三位{ABC} 前缀{A,AB} 后缀{BC,C},共同部分{Ø},next[3]=0;
在第四位{ABCD} 前缀{A,AB,ABC} 后缀{BCD,CD,D},共同部分{Ø},next[4]=0;
在第五位{ABCDA} 前缀{A,AB,ABC,ABCD} 后缀{BCDA,CDA,DA,A},共同部分{A},next[5]=1;
在第六位{ABCDAB} 前缀{A,AB,ABC,ABCD,ABCDA} 后缀{BCDAB,CDAB,DAB,AB,B},共同部分{AB},next[6]=2;
在第七位{ABCDABD} 前缀{A,AB,ABC,ABCD,ABCDA,ABCDAB} 后缀{BCDABD,CABD,ABD,BD,D},共同部分{Ø},next[7]=0;
这就是next的含义，下面我们来讲讲如何求这个值
1 void pre(){ 2 int k=0; 3 for (int i=2;i<=len2;++i){ 4 while (k>0&&t[k+1]!=t[i]) k=nxt[k]; 5 if (t[k+1]==t[i]) k++; 6 nxt[i]=k; 7 } 8 }
View Code
读者们也可以参照http://www.cnblogs.com/tangzhengyue/p/4315393.html来学习
三.kmp算法内容
好吧现在切入正题，前面都是铺垫
我们前面已经求出了next数组的值了，那么我们应该如何应用呢？
就像上面的这个字符串匹配，当匹配到了这里，D和上面空格并不匹配
前面“ABCDAB”是匹配的，那我们就按照下面这个式子
移动位数 = 已匹配的字符数 – 对应的部分匹配值
4 = 6 – 2
因为还是不能匹配，那我们继续向后移2=2-next[2]位
因为第一位不能匹配，直接向后移一位
最后匹配成功，因此我们可以发现，在原字符串中，每个字符都只匹配到了一次，时间复杂度为严格的O(n+m)
如还是不能理解可学习https://segmentfault.com/a/1190000007066358#articleHeader7
最后附上kmp部分的代码
1 void kmp(){ 2 int k=0; 3 for (int i=1;i<=len1;++i){ 4 while (k>0&&t[k+1]!=s[i]) k=nxt[k]; 5 if (t[k+1]==s[i]) k++; 6 if (k==len2) printf("%d ",i-len2+1),ans++; 7 } 8 }
View Code
四.总结
kmp算法的确是一个效率高，且较好理解的字符串匹配方法，对于解决这方面问题都非常有效
接下来希望读者也可以完成一些基础题目来巩固
http://poj.org/problem?id=2406
http://acm.hdu.edu.cn/showproblem.php?pid=2087
最后在推荐一个炒鸡强的一个大佬博客 http://www.cnblogs.com/whc200305/p/7580086.html