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

姚秀情

摘要：本文以實例出发分析了模式匹配kmp 算法以及算 法中next 函数的含义即形成过程，由定义出发，给出详实的参数来判定k的情况来计算next数组的值，从另一个角度更好的帮助学生理解该算法。

关键词：字符串匹配;kmp算法;next数组

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2019）03-0131-02

0 引言

数据结构是计算机专业一门非常重要的基础课程，KMP算法——字符串匹配算法是经典的算法，它指的是找出特定的模式串在一个较长的字符串中出现的位置[1]。其算法的主要核心是next数组值的计算，利用模式串对应的next 数组值，避免了匹配不成功时不必要的回溯，计算next数组的值对于初学者来说其过程晦涩难懂。

1 BF算法与kmp算法

1.1 BF算法简介

传统的BF算法为：如果当前字符匹配成功（即S[i]==P[j]），则i++，j++，继续匹配下一个字符;如果失配（即S[i]！=P[j]），令i=i-（j-1），j=0。相当于每次匹配失败时，i回溯，j被置为1。如有字符串S：iloveplay和模式串T：ilovx来说利用BF算法匹配到s[5]和t[5]时，i回溯至2，j被置为1表现出BF算法的致命的缺点例子，如表格1所示。

1.2 kmp算法的基本思想

用kmp算法的基本思想可以实现当S串iloveplay与T串ilovx在s[5]和t[5]失配时，直接用T[1]号元素与s串失配的字符s[5]进行匹配，因为i1=j1i2=j2i3=j3以此类推在i5≠j5失配之前都是两两相等的，且观察s串自身来说i1≠i2i2≠i3i3≠i4i4≠i5由此证明就j1≠i2j1≠i3j1≠i4，所以相对于S串有效地多往后面跳3个字符，加快了匹配速度，可以看出i是不需要回溯的，只需要回溯j就可以[2]，如表格2所示。

2 next数组描述

KMP算法防止了不必要的回溯不发生，它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。而子串中每一个元素随时都有可能发生不匹配的情况，当发生不匹配时该用子串的哪个元素去和主串匹配就是我们所说的next[j]数组，他指导着模式匹配下一步改用第几号元素去进行匹配。而模式串next数组值取决于模式串自身的特点，与被匹配的主串无关。

传统的next数组使用递推的思想，对于模式串T，且已知next[j]=k即T0Tk-1”=“Tj-kTj-1”时，next[j+1]=next[j]+1=k+1，但T0Tk-1Tk”≠ “Tj-kTj-1Tj”。换言之，当Tk！=Tj时，有长度为k+1的相同前缀后缀，不能再简单的令：next[j+1]=next[j]+1，这时若能在前缀“T0Tk-1Tk”中不断的递归k=next[k]，找到一个字符Tk使得Tk=Tj，且满足T0Tk'-1 Tk'=Tj-k'Tj-1Tj，从而next[j+1]=k+1=next[k']+1，否则next[j+1]=0。运用这个思想对字符串“edeedee”求出的next数组值为0，1，1，2，2，3，4从描述过程不难看出其抽象难懂，极易造成错误的结果。

3 next数组的定义法求解函数值

KMP算法相比于朴素的模式匹配算法，其改进之处在于：利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离[3]。设模式串为T1T2……Tj，，next函数的定义如下：

该方法严格从next数组的定义出发，模式串的下标j从1开始，当下标为1时，next[1]=0，当下标不为1时，根据模式串中字符的下标j确定k的取值范围，即1

4 结语

next数组代表了模式串与主串匹配失败时模式串向前滑动的距离数，在KMP算法中至关重要，本文重点阐述了由next数组的定义出发，给出了相应的判定方法及要点分析，计算出了next数组的值，与递推方法计算next数值完全吻合，在计算next数组值时提高了效率也方便理解。

参考文献

[1] 程杰.大话数据结构[M].北京：清华大学出版社，2011.

[2] 汤雅玲.KMP算法中next数组的计算方法研究[J].计算机技术与发展，2009（06）：98-101.

[3] 左飞.算法之美隐匿在数据结构背后的原理C++版[M].北京：电子工业出版社，2016.

Analysis of Next Array Value Computing in KMP Algorithms

YAO Xiu-qing

（Information Engineering College of Yango University，Fuzhou  Fujian  350015）

Abstract：This paper 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