浅析KMP算法中next数组值计算

1、    浅析kmp算法中next数组值计算    姚秀情摘要：本文以實例出发分析了模式匹配kmp 算法以及算 法中next 函数的含义即形成过程，由定义出发，给出详实的参数来判定k的情况来计算next数组的值，从另一个角度更好的帮助学生理解该算法。关键词：字符串匹配;kmp算法;next数组：tp301.6 ：a ：1007-9416（2019）03-0131-020 引言数据结构是计算机专业一门非常重要的基础课程，kmp算法字符串匹配算法是经典的算法，它指的是找出特定的模式串在一个较长的字符串中出现的位置1。其算法的主要核心是next数组值的计算，利用

2、模式串对应的next 数组值，避免了匹配不成功时不必要的回溯，计算next数组的值对于初学者来说其过程晦涩难懂。1 bf算法与kmp算法1.1 bf算法简介传统的bf算法为：如果当前字符匹配成功（即si=pj），则i+，j+，继续匹配下一个字符;如果失配（即si！=pj），令i=i-（j-1），j=0。相当于每次匹配失败时，i回溯，j被置为1。如有字符串s：iloveplay和模式串t：ilovx来说利用bf算法匹配到s5和t5时，i回溯至2，j被置为1表现出bf算法的致命的缺点例子，如表格1所示。1.2 kmp算法的基本思想用kmp算法的基本思想可以实现当s串iloveplay与t串ilov

3、x在s5和t5失配时，直接用t1号元素与s串失配的字符s5进行匹配，因为i1=j1i2=j2i3=j3以此类推在i5j5失配之前都是两两相等的，且观察s串自身来说i1i2i2i3i3i4i4i5由此证明就j1i2j1i3j1i4，所以相对于s串有效地多往后面跳3个字符，加快了匹配速度，可以看出i是不需要回溯的，只需要回溯j就可以2，如表格2所示。2 next数组描述kmp算法防止了不必要的回溯不发生，它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。而子串中每一个元素随时都有可能发生不匹配的情况，当发生不匹配时该用子串的哪个元素去和主串匹配就是我们所说的nextj数组，他

4、指导着模式匹配下一步改用第几号元素去进行匹配。而模式串next数组值取决于模式串自身的特点，与被匹配的主串无关。传统的next数组使用递推的思想，对于模式串t，且已知nextj=k即t0tk-1”=“tj-ktj-1”时，nextj+1=nextj+1=k+1，但t0tk-1tk” “tj-ktj-1tj”。换言之，当tk！=tj时，有长度为k+1的相同前缀后缀，不能再简单的令：nextj+1=nextj+1，这时若能在前缀“t0tk-1tk”中不断的递归k=nextk，找到一个字符tk使得tk=tj，且满足t0tk'-1 tk'=tj-k'tj-1tj，从而nextj

5、+1=k+1=nextk'+1，否则nextj+1=0。运用这个思想对字符串“edeedee”求出的next数组值为0，1，1，2，2，3，4从描述过程不难看出其抽象难懂，极易造成错误的结果。3 next数组的定义法求解函数值kmp算法相比于朴素的模式匹配算法，其改进之处在于：利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离3。设模式串为t1t2tj，next函数的定义如下：该方法严格从next数组的定义出发，模式串的下标j从1开始，当下标为1时，next1=0，当下标不为1时，根据模式串中字符的下标j确定k的取值范围，即1<k<j，在k的取值范围内判定每一

6、个k值判断等式t1t2tk-1与tj-k+1tj-k+2.tj-1是否成立，若成立，则当前的k值符合条件，然后在所有符合条件的k值中取最大值，即nextj值，若等式不成立，则函数的返回值为1。同样有模式串edeedee，它的下标分别为1，2，3，4，5，6，7由数组的定义求出next函数值，其过程如表格3所示。< p>4 结语next数组代表了模式串与主串匹配失败时模式串向前滑动的距离数，在kmp算法中至关重要，本文重点阐述了由next数组的定义出发，给出了相应的判定方法及要点分析，计算出了next数组的值，与递推方法计算next数值完全吻合，在计算next数组值时提高了效率也方便

7、理解。参考文献1 程杰.大话数据结构m.北京：清华大学出版社，2011.2 汤雅玲.kmp算法中next数组的计算方法研究j.计算机技术与发展，2009（06）：98-101.3 左飞.算法之美隐匿在数据结构背后的原理c+版m.北京：电子工业出版社，2016.analysis of next array value computing in kmp algorithmsyao xiu-qing（information engineering college of yango university，fuzhou  fujian  350015）abstract：this pa

8、per analyses the meaning of the pattern matching kmp algorithm and the next function in the algorithm， that is， the formation process. starting from the definition， it gives detailed parameters to determine k to calculate the value of the next array， which can help students better understand the algorithm from another angle.key words：string matching; kmp algorithm; next array数字技术与应用2019年3期