关于kmp算法改进的探讨

摘要：本文以模式串t是否有重复的几种不同情况的例子，分析了模式匹配算法kmp的形成过程，将较难理解的next函数的计算融入到算法中去，对算法做了一点改进，改进后的算法遵循kmp算法主串指针不回溯的原则，但却更容易理解。

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

中图分类号：TP301.6   文献标识码：A    文章编号：1007-9416（2020）04-0000-00

1 引言

KMP算法是一种字符串比较算法，相对于BF算法，它有比较大的改进，也是一款经典的算法，且它在计算机应用系统中如文本编辑、情报检索、自然语言翻译有着广泛的应用[1]，是每一个想学习字符串匹配的人必须要了解的一个算法，但相信很多人初识KMP算法的時候都是知其然而不知其所以然，对于其next[j]数组更是一头雾水。

2 kmp 算法的研究与分析

2.1 kmp算法的概述

对于朴素的模式匹配算法即BF算法，它的基本思想是：有主串s和模式串（子串）t，要求找出模式串t在s串中的首次出现的位置。若当前字符匹配成功（即s[i] == t[j]，i为主串的下标，j为模式串的下标），则i++，j++，继续匹配下一个字符;如果失配（即s[i]！ = t[j]），令i回溯到 i-j+1的位置，j回到模式串起始字符位置，这样的算法比较次数多，相当耗时。为了提高效率KMP算法对BF算法做了改进，其核心思想就是减少比较的次数即让主串s没必要的回溯不发生，它的最大改进在于在匹配过程中失配的情况下，将模式串t有效地多往后面跳几个字符，加快匹配速度，那究竟能有效的往后面跳几个字符来减少次数呢，kmp算法认为，匹配过程与模式串的特征关系密切，如果对于模式串中存在一个整数k（k

2.2 kmp算法的形成过程分析

在以下例子中s串的下标i与t串的下标j都是从1开始。

第一种情况是t串在失配字符前没有重复字符的情况时：第一次匹配是s串iambabynigthowl与t串iambe在下标为5的元素失配时（即s[5]！=t[5]），直观t串失配字符前的几个元素发现并不相等，即t[1] ≠t[2] ≠ t[3] ≠t[4]，而在失配前s串与t串的前4个字符一一对应，所以可以判断出t[1]字符与s串的前四个字符都不相同，所以第二次比较直接将t[1]字符与s[5]字符开始比较即可，子串向右滑动了4个字符，相比于BF算法，s串的下标i没有回到s[2]的位置重新与t[1]字符开始比较，比较次数减少了三次。

第二种情况是t串在失配字符前有一个字符重复时，s串www.baidu与t串ww.在下标为3的位置失配时，按照第一种情况应该把s[3]与t[1]匹配，匹配不成功，但却会错过它的正确匹配的位置，即s[2]与t[1]开始进行匹配后发现，s[2]=t[1]、s[3]=t[2]、s[4]与t[3]，模式串向右滑动了1个字符，找到模式串在主串中的起始位置为2.

第三种情况是t串在失配字符前有两个字符重复时：s串absabsqueen和t串absabc在下标为6的位置失配时，下一个与s[6]要进行匹配的t串字符应该是哪一个呢，通过观察会发现在t串失配字符前有两个字符是重复的，即t[1]= t[4]、t[2]= t[5]，而t[4]=s[4]、t[5]=s[5]，所以t[1]=s[4]、t[2]=s[5]，t[3]会不会和s[6]匹配，要经过比较后才知道，所以不能放过任何一种可能性，应该尝试把重复部分的后一个字符与s[6]进行匹配，模式串t向右滑动了5个字符，减少了4次匹配次数。

第四种情况是t串在失配字符前所有的字符都相同时：对于特殊字符s串ssssanmx和t串ssssb，在失配的下标为5的位置的字符前的字符串有最长三个字符重复，正常情况下，仍然可以直接用T[4]号元素与s串失配的字符进行匹配，发现t[4]与s[5]仍然失配，且t[4]= t[3]= t[2]= t[1]，没有必要让t[3]、t[2]、t[1]都与s[5]匹配一次，直接将t[1]与是s[6]进行匹配，提高了效率。

从以上分析过程中不难发现为了求出第j个字符前最长长度相等的公共元素k，kmp算法引进了一个next函数[3]，next[j]即表示了t串中的第j个字符与主串s中相应字符失配时，在模式串t中需要重新和主串s中该字符进行比较的字符位置。因此next函数的求解过程是kmp算法的关键，尽管next函数值可以用递归和next函数本身的定义出发对它进行计算，但其过程还是比较难理解，若加上其代码的形成过程，更是让众多初学者感觉是懂非懂，因此本文对kmp算法提出了一点改进，对于k值，不用next函数对其进行求解，而是把k值的计算融入到算法中去，主观上更容易理解其匹配过程，而代码看起来也更简洁易懂。

3 kmp算法的改进

改进的算法的过程如下：

（1）遵循kmp算法的指导思想，主串s与模式串t匹配时，当发生失配时，寻找下一个与s串失配字符匹配的t串字符时，主串s的下标i不回溯。

（2）主串字符s[i]与模式串字符t[j]匹配发生失配时，设置变量k使得主串s[k]，（i-j+2<=k

（3）若模式串t的下标j大于模式串的长度时则表示在主串中找到了模式串。

其改进的算法代码如下：

输入一个字符串s为主串;

输入一个字符串t为模式串;

i=1;

j=1;

While （i<=len（s） && j<=len（t）） //len（s）为主串s长度，len（t）为模式串t的长度

{    if（s[i]=t[j]）

{i++;

j++

}

else

{ k=i-j+2;

j=1;

I++;

While （k

{if（s[k]==t[j]）

{K++;

j++;}

Else

{k++;

j=1;

}

}

}

}

4 改進算法可行性

取主串s为qvqbqvcbdw，模式串t为qvcbd时，当初始值都为1时s[1] =t[1]， i和j的值各加1，i=2，j=2，根据改进算法的程序，这样循环比较直至s[3] ≠t[3]时，重新置j=1，k=i-j+2=2，i加1后i=4，这时k的值小于i且j的值小于t串的长度，将t[1]的值与s[k]即s[2]的值进行比较后t[1]≠s[2]，k值加1后k=2+1=3，j重新置1即j=1，这时k的值小于i且j的值小于t串的长度，将s[k]即s[3]与t[1]比较后s[3] =t[1]，k的值加1即k=3+1=4，j的值加1后j=2，这时k的值不小于i，条件不满足，回到程序起始状态，将t串第二个字符与s串的第四个字符比较，s[i]即s[4]的值与t[2]的值进行比较，但s[4] ≠t[2]，k的值为k=4-2+2=4， j重新置1即j=1，i的值加1后i=5，这时k的值小于i， 将s[k]即s[4]与t[1]进行比较，s[4] ≠t[1]，k值加1后k=4+1=5，j重新置1即j=1，这时k的值不小于i，条件不满足，回到程序起始状态比较s[5]与t[1]的值后s[5]=t[1]，i和j的值各加1，i=5，j=2，接着比较s[6]和t[2]的值依然相等，以此类推，直至比较到s[8]=t[5]后，j的值大于t串的长度，找到模式串在主串的起始位置为5，其比较次数如表 1所示：

以上例子对改进的算法进行了验证，发现其能遵循i不回溯的原则，比较的次数与使用KMP算法的字符匹配的次数相同，模式串右移了尽可能最大的距离，且其时间复杂度为O（m+n），这样的比较过程在直观上更易于理解，且同样能达到匹配字符串的效果。

参考文献

[1].潘群娜.基于模式匹配KMP算法的探讨[J].科技信息（科学教研），2007（13）：335+377.

[2].李莉，江育娥，林劼，等.基于KMP算法的改进算法KMPP[J].计算机工程与应用，2016，52（8）：33-37.

[3].周雅翠，孙磊.基于KMP算法的next函数理解与分析[J].吉林建筑工程学院学报，2012，29（1）：79-82.

收稿日期：2020-03-23

作者简介：姚秀情（1980—），女，福建闽清人，本科，实验师，从事计算机基础教学工作。

On the Improvement of KMP Algorithm

YAO Xiu-qing

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

Absrtact： This paper analyzes the formation process of pattern matching algorithm KMP with several different examples of whether pattern string t has repetition. It integrates the calculation of next function which is difficult to understand into the algorithm， and makes a little improvement on the algorithm. The improved algorithm follows the principle of no backtracking of main string pointer of KMP algorithm， but it is easier to understand.

Keywords： string matching; next array; algorithm improvement