【菜鸟福音】KMP算法简单理解(从严蔚敏老师的《数据结构》出发
导言:本文有以下特点: (1)主要讨论的是严蔚敏老师的《数据结构》中第四章所提到的KMP算法,即带NEXT[]辅助数组的KMP算法; (2)主要针对初学者,对算法不熟悉的同学,主要目的是希望通过本文能让初学者快速理解KMP算法的NEXT的计算规则。
最近复习到KMP算法,发现之前虽然好不容易弄会了手动KMP计算NEXT而且自以为“理解”了KMP算法,结果复习起来发现基本要重看。痛定思痛,决定彻底弄懂这个玩意儿。
相信即使是初学者也能理解KMP算法的最大优势在于不需要将模式串回退匹配来提高速度。如果给出了NEXT数组,我估计绝大部分人都能够手动模拟搜索过程。
但问题就在于,怎么计算next数组呢?
严老师的书上给出了一种对next的计算算法。算法固然是很简单的,重点在于解释的过程。
我们先回顾一下书上的做法。 书上从一种匹配情况出发。 这种匹配情况中,已知在一次匹配的过程中有(每个字符写作p[]) ‘p[1]p[2]..p[k]’=‘..p[j]’(即某段字符相等匹配),并且已知p[j]的next[p[j]]的值为p[k]。 然后再考虑p(k+1)和p(j+1)的匹配情况。 书上的讲解虽然易懂,但是将其直接推演到求解一个模式串的next值得情况时则有些让人摸不着头脑:一个串和自己相比,又是错位相比,还是在知道某段值得情况下"向前看"去求下一个字符的next[],这是在是不好想象。 即使拿一个具体的例子来看,比如abbab。想要模拟一下这种假设,都让人手忙脚乱。 当然,如果算法基础比较好的同学也许分分钟搞定了这个问题,但是对于我这种来说...就需要另一个想法了!
那么来看看我的办法。 首先,让我们厘清KMP算法中next[]的意义吧。 next数组中的某个值next[k]的意义在于指出匹配失败时下一次匹配的模式串字符的位置. 它实际上是,当模式串中的p[k]与文本串(目标串)t[j]对比时,如果不能匹配,在将模式串右移的过程中,第一个遇到"合理的"的再一次与t[y]比较的模式串上的字符的位置,即p[next[k]]。 这个地方的合理性在于,从p[next[k]]之前的所有模式串字符,与当前位置下的目标串前面的一部分是完全相同的,即 'p[1]p[2]...p[next[k]-1]' = '...t[j-1]' = '...p[k-1]' 厘清合理性后,让我们来看看怎么求next[]。
对于一个模式串p[],我们很容易通过定义对其头两个字符的next进行赋值(*:如果第一个字符都不匹配,那么只能讲模式串右移;如果第二个字符不能匹配,那么只能再与第一个字符比较),在此处还是写作p[1]=0,p[2]=1;。 现在,假设我们已经对p[k]及其之前的每个字符都求得了next[]的值(这种假设是合理的,因为我们显然已经求得了p[1]、p[2]的next[]),那么我们现在来考虑p[k+1]对应的next值,即next[k+1]=x。 回顾定义,x应当是这样一个值:它能使得,当模式串与目标串已经匹配了k个字符时,即 'p[1]p[2]...p[k-1]p[k]'='...t[j-1]t[j]' 如果p[k+1]!=t[j+1],那么p[x]就是下一个与t[j+1]比较的字符。 根据前面提到的合理性,此时,即移动后的模式串,在p[x]前的那些字符,是与目标串上相应位置上的字符相匹配的,即有: 'p[1]p[2]...p[x-1]' = '...t[j-1]' = '...p[k]' 注意,此时也就是有 'p[1]p[2]...p[x-1]'='...p[k]'。 此时相等意义正是理解算法的关键。 因为已经说过此时求得了p[k]的next[k]=y为已知,而这个y的意义由前面的合理性知道,有 'p[1]p[2]..p[y-1]'='...p[k-1]' 如果此时再满足:p[y]=p[k],那么此时有: 'p[1]p[2]..p[y-1]p[y]' = '...p[k-1]p[k]' = 'p[1]p[2]...p[x-1]' 也就是说此时满足了如下条件y=x-1!(由KMP的“最长部分匹配”条件可以得此时的推导是充要的,本文重在理解,此处的推理也就不证明啦)。那么我们就求得了 next[k+1]=x=y+1=next[k]+1 这就是严老师教材所给出的公式,不过严老师教材中的推理好比从后向前看,这里更多的是从前向后看。 不过这个过程还没结束,如果p[y]!=p[k]怎么办?,注意,此时我们有 'p[1]p[2]..p[y-1]'='...p[k-1]' 所以p[y]的next值即next[y]同样满足前面说到的合理性,因此可以有y2=next[y],继续递归...直到,最后一个yn=1。
整个过程就好比一个解方程的过程,有方程特征(即next[]的性质和KMP的性质),有初值和边界条件(即p[k]及之前的字符的next[]值已知,且当第一个字符不匹配时模式串右移),那么就可以求得P[K+1]的next[]值。
这个理解就写到这里啦,有许多地方数学的表达不严谨,重在理解嘛。 如有勘误,请指正。欢迎讨论!
谢谢阅读!
??
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- 角度2单元测试组件与routerLink
- AngularJS ng-repeat下使用ng-model
- axis2通过城市名称调用.net写的asmx WebService查询天气实例
- 关于bootstrap的treeview不显示多选(复选框)的问题,以及联
- Angular2:使用Observables进行多次同步调用的最佳方法是什
- Unix/Linux中的jar提取的最佳方法?
- bootstrap之Drag
- 《数据结构》静态链表类的定义参考代码
- ssh – 无需运行bash_profile或bashrc即可登录
- 解决: is not found. Have you run APT to generate&n