使用KMP算法匹配字符串的关键就是正确计算出next数组(不清楚何为模式匹配何为KMP算法什么是next数组可以自行百度或参考数据结构教科书)。next数组的计算是一大难点殷人昆的数据结构教科书中对此问题的论述不够清晰所列代码和说明部分关联性不强看了让人似懂非懂。自己花了很长时间琢磨next数组计算的问题现在总算从头到尾弄明白了于是就在这里将自己的思考所得与大家分享。现有长为M的模式串Pa0 a1 —– aM-1,记P在索引ij之间的部分(包括i,j)为P[i,j],要求模式串P[0,M-1]的next数组的各元素next[0]—-next[M-1]。首先next[0]-1(为什么取-1下面有说明),根据next数组的定义对j1,next[j]为串P[0,j-1]的最长相等前后缀子串的长度(对串b0,b1,–,bn,满足b0,–,bkbn-k,–,bn-1,bn 0kn 的所有相等前后缀子串中的最长者b0,–,bk和bn-k,–,bn-1,bn即为串b0,b1,–,bn的最长相等前后缀子串其长度为k1)若串P[0,j-1]不存在相等的前后缀子串(当然也就不存在最长相等前后缀子串)则令next[j]0。由于我们最先知道next[0]-1,所以自然就可以考虑在next[0],—,next[j]已知的情况下推算next[j1]的值我们来看下图这幅图可以给我们一些启发。如图所示假定j1,我们先考虑K1next[j],若K10则串P[0,j-1]中不存在相等前后缀子串这意味着串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串因为假若存在去掉前缀最后一个元素和后缀最后一个元素P[j]剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串矛盾。于是串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]下面我们检查是否有p[0]p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串因而就为串P[0,j]的最大相等前后缀子串其长度为1故next[j1]1.若不是,则说明p[0,j]中不存在相等前后缀子串从而next[j1]0,如果K10则K1就为串P[0,j-1]的最长相等前后缀子串A1B1的长度也是A1最末元素下一位置的索引。我们检查P[K1]是否和P[j]匹配若匹配则A1和P[K1]构成的子串和B1和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串这是因为假若还存在更长的串P[0,j]的相等前后缀子串去掉前缀最末元素和后缀最末元素P[j]则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串其长度大于A1B1矛盾。于是串P[0,j]的最长相等前后缀子串的长度就是K11,因而next[j1]K11,这样我们就求出了next[j1].如果P[K1]和P[j]不匹配,我们令K2next[K1],若K20则A1中不存在相等前后缀子串于是串P[0,j-1]中不存在比A1,B1更小的相等前后缀子串因为如果存在则后缀与前缀构成了A1的相等前后缀子串矛盾。这样A1B1构成了串P[0,j-1]的唯一的相等前后缀子串但P[K1]和P[j]不匹配故串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串因为假若存在去掉前后缀最末元素得到串P[0,j-1]的一对相等前后缀子串它只能是A1B1但假设存在的P[0,j]中长度大于2小于等于j的相等前后缀子串的前缀和后缀的最末元素相互匹配于是A1B1下一位置上的元素相互匹配即P[K1]和P[j]匹配矛盾。这样串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]下面我们检查是否有p[0]p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串因而就为串P[0,j]的最大相等前后缀子串其长度为1故next[j1]1.若不是,则说明p[0,j]中不存在相等前后缀子串从而next[j1]0若K20则K2就是A1的最长相等前后缀子串A2C2的长度也是A2最末元素下一位置的索引.C2在B1中有相应的镜像B2则A2B2构成了串P[0,j-1]第二长的相等前后缀子串这是因为假若A2B2不是串P[0,j-1]第二长的相等前后缀子串那么必有串P[0,j-1]的相等前后缀子串其长度介于A1B1和A2B2之间其前后缀构成了A1的一对相等前后缀子串注意其长度长于A2B2和A2C2于是矛盾。下面我们检查P[K2]是否和P[j]匹配若匹配则A2和P[K2]构成的子串和B2和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串这是因为假若还存在更长的串P[0,j]的相等前后缀子串去掉前缀最末元素和后缀最末元素P[j]则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串其长度大于A2B2因而它只能是A1B1注意我假设存在的更长的串P[0,j]的相等前后缀子串的前后缀的最末元素相互匹配因此A1B1的下一位置的元素相互匹配即P[K1]和P[j]相互匹配矛盾。这样串P[0,j]的最长相等前后缀子串的长度就是K21,因而next[j1]K21,这样我们就求出了next[j1].如果P[K2]和P[j]不匹配,我们令K3next[K2],若K30则A2中不存在相等前后缀子串于是串P[0,j-1]中不存在比A2,B2更小的相等前后缀子串因为如果存在则后缀与前缀构成了A2的相等前后缀子串矛盾。注意P[K2]和P[j]不匹配故串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串因为假若存在去掉前后缀最末元素得到串P[0,j-1]的一对相等前后缀子串它只能是A1,B1和A2B2中的一个而我假设存在的串P[0,j]中长度大于2小于等于j的相等前后缀子串的前缀后缀的最末元素相互匹配这意味着A1B1和A2B2中必有一个其前后缀的最末元素的下一位置上的元素相互匹配这和P[K2]和P[j]以及P[K1]和P[j]不匹配矛盾。这样串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]下面我们检查是否有p[0]p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串因而就为串P[0,j]的最大相等前后缀子串其长度为1故next[j1]1.若不是,则说明p[0,j]中不存在相等前后缀子串从而next[j1]0若K30则K3就是A2的最长相等前后缀子串A3C3的长度也是A3最末元素下一位置的索引.C3在B2中有相应的镜像B3则A3B3构成了串P[0,j-1]第三长的相等前后缀子串这是因为假若A3B3不是串P[0,j-1]第三长的相等前后缀子串那么必有串P[0,j-1]的相等前后缀子串其长度介于A2B2和A3B3之间其前后缀构成了A2的一对相等前后缀子串注意其长度长于A3B3和A3C3于是矛盾。下面我们检查P[K3]是否和P[j]匹配若匹配则A3和P[K3]构成的子串和B3和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串这是因为假若还存在更长的串P[0,j]的相等前后缀子串去掉前缀最末元素和后缀最末元素P[j]则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串其长度大于A3B3因而它只能是A1B1A2B2中的一个注意我假设存在的更长的串P[0,j]的相等前后缀子串的前后缀的最末元素相互匹配因此A1B1,A2B2中必有一个其前缀后缀的最末元素的下一位置上的元素相互匹配这和P[K2]和P[j]以及P[K1]和P[j]不匹配矛盾。这样串P[0,j]的最长相等前后缀子串的长度就是K31,因而next[j1]K31,这样我们就求出了next[j1].如果P[K3]和P[j]不匹配,我们令K4next[K3]若K40……………………………………我们令Kmnext[Km-1],若Km0则Am-1中不存在相等前后缀子串于是串P[0,j-1]中不存在比Am-1,Bm-1更小的相等前后缀子串因为如果存在则后缀与前缀构成了Am-1的相等前后缀子串矛盾。注意P[Km-1]和P[j]不匹配故串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串因为假若存在去掉前后缀最末元素得到串P[0,j-1]的一对相等前后缀子串它只能是A1,B1,A2B2,…………Am-1,Bm-1中的一个而我假设存在的串P[0,j]中长度大于2小于等于j的相等前后缀子串的前缀后缀的最末元素相互匹配这意味着A1B1,A2B2,…………Am-1,Bm-1中必有一个其前后缀的最末元素的下一位置上的元素相互匹配这和P[K1]和P[j],P[K2]和P[j],…………,P[Km-1]和P[j]不匹配矛盾。这样串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]下面我们检查是否有p[0]p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串因而就为串P[0,j]的最大相等前后缀子串其长度为1故next[j1]1.若不是,则说明p[0,j]中不存在相等前后缀子串从而next[j1]0若Km0则Km就是Am-1的最长相等前后缀子串AmCm的长度也是Am最末元素下一位置的索引.Cm在Bm-1中有相应的镜像Bm则AmBm构成了串P[0,j-1]第m长的相等前后缀子串这是因为假若AmBm不是串P[0,j-1]第m长的相等前后缀子串那么必有串P[0,j-1]的相等前后缀子串其长度介于Am-1Bm-1和AmBm之间其前后缀构成了Am-1的一对相等前后缀子串注意其长度长于AmBm和AmCm于是矛盾。下面我们检查P[Km]是否和P[j]匹配若匹配则Am和P[Km]构成的子串和Bm和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串这是因为假若还存在更长的串P[0,j]的相等前后缀子串去掉前缀最末元素和后缀最末元素P[j]则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串其长度大于AmBm因而它只能是A1B1A2B2,…………,Am-1,Bm-1中的一个注意我假设存在的更长的串P[0,j]的相等前后缀子串的前后缀的最末元素相互匹配因此A1B1,A2B2,…………,Am-1,Bm-1中必有一个其前缀后缀的最末元素的下一位置上的元素相互匹配这和P[K1]和P[j],P[K2]和P[j],…………,P[Km-1]和P[j]不匹配矛盾。这样串P[0,j]的最长相等前后缀子串的长度就是Km1,因而next[j1]Km1,这样我们就求出了next[j1].如果P[Km]和P[j]不匹配,我们令Km1next[Km]若Km10………………以此类推按照上述步骤不断进行下去注意到jK1K2……Km…… 所以我们在上述过程中得到的前缀子串A1,A2,——-,Am—-的长度严格递减由于长度不能为负所以上述过程不可能无限进行下去必然在有限步后终止。也就是说在操作有限步后要么遇到下图所示的情况这里我们最终得到串P[0,j-1]的最短相等前后缀子串An,Bn,但p[Kn]和P[j]无法匹配,于是仿照以上分析令Kn1next[Kn],由于An,Bn为最短相等前后缀子串所以这里必有Kn10.这样我们检查p[0]和p[j]是否相等若是则next[j1]1,否则next[j1]0。这样next[j1]就求出了。要么遇到下图所示情况这里我们最终得到串P[0,j-1]的第m长相等前后缀子串Am,Bmp[Km]和P[j]能够相互匹配根据以上分析知next[j1]Km1,这样next[j1]就求出了。要么遇到下图所示情况按照以上分析此时检查P[0]和P[j]是否相等若是则next[j1]1,否则next[j1]0,这样next[j1]就求出了。综上可以总结出在已知next[0],next[1],—,next[j]的情况下计算next[j1]的算法如下(j1):(1)将j赋值给k(2)如果next[k]等于01如果模式串在索引0处的字符和在索引j处的字符匹配1赋值给next[j1]如果模式串在索引0处的字符和在索引j处的字符不匹配0赋值给next[j1]2算法结束如果next[k]不等于01如果模式串在索引next[k]处的字符和在索引j处的字符匹配{1} next[k]加一赋值给next[j1]{2} 算法结束如果模式串在索引next[k]处的字符和在索引j处的字符不匹配{1}next[k]赋值给k{2}转(2)上述用自然语言描述的算法的JAVA代码是(pat表示模式串P)int kj; while(true) { if (next[k]0) { if (pat.charAt(0)pat.charAt(j)) next[j1]1; else next[j1]0; break; } else { if (pat.charAt(next[k])pat.charAt(j)) { next[j1]next[k]1; break; } else { knext[k]; } } }以上在已知next[0],next[1],–,next[j]的情况下求next[j1]的代码对j1是适用的但在j0时(即已知next[0]求next[1])无效因为以上代码在首次进入循环后运行到11行时出现了pat.charAt(-1)这样的字符串越界访问解决这个问题也很简单把11行改写为if (next[k]-1 || pat.charAt(next[k])pat.charAt(j))就可以了。这样j0时next[1]的值能正确求出(就是0),这也是为什么next[0]-1的原因因为此时若next[0]-1,则next[1]的值就能正确求出。此外这样改写对j1时next[j1]的求解没有任何影响这是因为j1时代码运行到11行时表达式next[k]-1的值总为false,这样if (next[k]-1 || pat.charAt(next[k])pat.charAt(j))等价于if (pat.charAt(next[k])pat.charAt(j))匹配判断是能够正常进行的现在我们可以写出完整的计算next数组的代码了:代码一package nextcompute; import java.util.*; public class nextcom { public static void main(String[] args) { String pat; Scanner inputnew Scanner(System.in); System.out.println(请输入模式串); patinput.nextLine(); int[] nextnew int[pat.length()]; next[0]-1; for (int j0; jpat.length()-1; j) { int kj; while(true) { if (next[k]0) { if (pat.charAt(0)pat.charAt(j)) next[j1]1; else next[j1]0; break; } else { if (next[k]-1 || pat.charAt(next[k])pat.charAt(j)) { next[j1]next[k]1; break; } else { knext[k]; } } } } for (int s: next) { System.out.print(s ); } System.out.println(); } }程序将模式串读入String对象pat然后计算pat对应的next数组。外层for循环的每一轮循环根据next数组前j1个值计算next[j1],内层while循环用于next[j1]的具体计算运行结果可以验证这是正确的为了得到数据结构教科书上给出的简洁形式我们还需要将代码一进行等价转换。设想如果每次进入内层while循环前knext[j],那么代码一20行30行32行的next[k]完全可以用k替换,第17行代码可以删除,代码一的knext[k]保持不变这是因为在代码一中执行knext[k]后访问next[k]和在修改的代码中执行knext[k]后访问k实际上是一样的此外还需要保证内层while循环结束前(也就是next[j1]算出时)knext[j1],j变为j1(为下一轮计算next[j2]作准备),因此代码一可以等价地改写如下代码二package nextcompute; import java.util.*; public class nextcom2 { public static void main(String[] args) { String pat; Scanner inputnew Scanner(System.in); System.out.println(请输入模式串); patinput.nextLine(); int[] nextnew int[pat.length()]; int j, k; next[0]-1; j0; k-1; while (jpat.length()-1) { while(true) { if (k0) { if (pat.charAt(0)pat.charAt(j)) { next[j1]1; j; k1; } else { next[j1]0; j; k0; } break; } else { if (k-1 || pat.charAt(k)pat.charAt(j)) { next[j1]k1; k; j; break; } else { knext[k]; } } } } for (int s: next) { System.out.print(s ); } System.out.println(); } }注意初始条件next[0]-1; j0; k-1;j0是因为要先由next[0]推算next[1],再由next[0],—,next[j]推算nextj1,k-1是因为首次进入外层while循环后第一次进入内层while循环前k应等于next[0]-1可以验证代码二的运行结果和代码一是一样的进一步分析代码二可以发现代码二中内层嵌套的while循环34行43行的break完全可以去掉并且24-26行30-32行40-42行可以写成更紧凑的形式这样我们可以把代码二改写成等价的代码三:代码三package nextcompute; import java.util.*; public class nextcom3 { public static void main(String[] args) { String pat; Scanner inputnew Scanner(System.in); System.out.println(请输入模式串); patinput.nextLine(); int[] nextnew int[pat.length()]; int j, k; next[0]-1; j0; k-1; while (jpat.length()-1) { if (k0) { if (pat.charAt(0)pat.charAt(j)) { next[j]k; } else { next[j]0; } } else { if (k-1 || pat.charAt(k)pat.charAt(j)) { next[j]k; } else { knext[k]; } } } for (int s: next) { System.out.print(s ); } System.out.println(); } }可以验证运行结果和代码一一致进一步地我们很容易就可以把代码三等价地改写成代码四代码四package nextcompute; import java.util.*; public class nextcom4 { public static void main(String[] args) { String pat; Scanner inputnew Scanner(System.in); System.out.println(请输入模式串); patinput.nextLine(); int[] nextnew int[pat.length()]; int j, k; next[0]-1; j0; k-1; while (jpat.length()-1) { if (k-1 || pat.charAt(k)pat.charAt(j)) { next[j]k; } else { if (k0) next[j]0; else knext[k]; } } for (int s: next) { System.out.print(s ); } System.out.println(); } }运行结果仍然和代码一相同。代码四形式非常简洁但是仍然可以继续化简注意到代码四第25行k0为真时完全可以继续执行knext[k],最后会在21行执行next[j]0,效果和第25行为真时执行next[j]0完全相同故25-28行可统一写为knext[k],从而得到形式最为简洁的代码五package nextcompute; import java.util.*; public class nextcom4 { public static void main(String[] args) { String pat; Scanner inputnew Scanner(System.in); System.out.println(请输入模式串); patinput.nextLine(); int[] nextnew int[pat.length()]; int j, k; next[0]-1; j0; k-1; while (jpat.length()-1) { if (k-1 || pat.charAt(k)pat.charAt(j)) { next[j]k; } else { knext[k]; } } for (int s: next) { System.out.print(s ); } System.out.println(); } }这(代码五)就是数据结构教科书上给出的next数组计算的代码实现这样通过层层分析我们就确定了next数组计算代码的最简形式也就是在各类文献资料书籍中最常见的形式。字符串模式匹配的KMP算法中next数组计算方法的详细分析到此结束笔者水平有限若有错误和纰漏恳请指正谢谢。