基于KMP算法的next数组.docVIP

基于KMP算法的next数组 　　摘要：?文主要叙述了基于KMP算法的next数组的理解，分析了在C++环境中利用next数组对KMP算法的具体实现，使该算法更加方便实用。 　　关键词：KMP算法；next数组；匹配 　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）03-0066-01 　　1 概述 　　字符串匹配是现代科学中的基本问题，如文献目录检索系统与生物基因序列匹配工程。对于这一问题的研究，D.E.Knuth，J.H.Morris和V.R.Pratt改进了Brute-Force算法，提出一种线性时间复杂的字符串匹配算法――KMP算法，该算法利用了上一次匹配失败的反馈信息，通过模式串对应的next数组减少回溯，成功地将时间复杂度由O（m*n）降低至O（m+n），从而达到快速匹配。 　　2 next数组的定义 　　next数组作为KMP算法中的关键，其特点是模式串每一位对应的next值仅依赖模式串本身，而与主串无关。普遍定义[1]如下： 　　[next[j]=-1 j=0max{k|1≤kj∧T0T1…Tk-1=Tj-kTj-k+1…Tj-1} 集合不为空0 其他] 　　其中模式串T（T0T1…Tm，m≥0）中每一个Tj （0≤j≤m）对应的next值以next[j]表示。 　　3 next数组的理解 　　1）由next数组的定义可知，每个模式串都有对应的唯一确定的next数组。对next数组可从两个方面来理解：next数组是用来记录字符串匹配过程中匹配失败情况下可以向前多跳几个字符（模式串本身局部匹配的信息）；next数组是用来描述模式串的对称程度的，数组的值越大，对称程度越高。 　　2） next数组的实现采用了递推思想，即以赋值定义next[0]=0为起点，通过next[0]算出next[1]的值，进而得到next[2]、next[3]、……、next[i]的值。 　　假设已求得next[j]=k，根据定义可得”T0T1…Tk-1”=” Tj-kTj-k+1 …Tj-1”，那么求next[j+1]的值可以分为以下两种情况： 　　1°若Tk= Tj，则”T0T1…Tk”=” Tj-kTj-k+1 …Tj”，并且不可能存在k’k满足上式，那么next[j+1]=k+1，即next[j+1]=next[j]+1。 　　2°若Tk！= Tj，则”T0T1…Tk”！=” Tj-kTj-k+1 …Tj”。设k=k1时，满足Tk1=Tj，下求k1。 　　 　　图1 图2 　　由图1可知实际上就是将模式串T往右移，移动后T’的j对应T的k1。 　　考虑另一个前提条件：”T0T1…Tk1-1”=” Tj-k1Tj-k1+1 …Tj-1”。实际上k1=next[k]，但满足了上述条件不一定就满足Tk1=Tj。也就是说仅移动一次不一定满足Tk1=Tj。如果移动一次后得到k1仍然不满足Tk1=Tj，就要按照前提条件再移动一次。 　　由图2，依此类推，直到Tkn=Tj或kn=0为止。此时有next[j+1]= kn+1，而kn=next[kn-1]且k1=k=next[j]，由于knkn-1…k1=kj，因此当需要求next[j+1]时，next[j]、next[k1]、 next[k2]…… next[kn]都已经求出来了。 　　4 有关next数组的题目解法 　　例.在KMP模式匹配算法中，需要求解串中P的next函数值，其定义如下（其中j为模式中符号的序号）。对于模式串”abaabaca”，其next函数值序列为多少。 　　[next[j]=0 j=1max{k|1kj∧T1T2…Tk-1=Tj-k+1Tj-k+2…Tj-1} 集合不为空1 其他] 　　解 首先把字符串填入到一个表格中， 　　 　　将j导入next函数，即可求解。 　　如j=1时，next[1]=0； j=2时，1kj，整数k不存在，next[2]=0； j=3时，1k3，只能取k=2（T1=T2），即”a”=”b”，不成立，舍去。于是整数k不存在，next[3]=0； j=4时，1k4，先取k=3（T1T2=T2 T3）， （下转第82页） 　　（上接第66页） 　　即”ab”=”ba”，不成立，舍去。再取k=2（T1=T3），即”a”=”a”，成立。于是max{k}=2，即next[4]=2； 　　同理可得next数组中其他元素的值。 　　所以结果为： 　　 　　5 next数组在C++环境下的实现 　　通过递推思想得到的计算next数组算法用C++语言描述如下： 　　void makeNext（const char P[]，int next[]） 　　{i