关于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<j），使得模式串t中第K个字符之前的k个字符（t[0]，t[1] ...t[k-1]）依次与t[j]的前面k-1个字符（t[j- k] t[j-k+1]...t[j-1]）相同，并与主串s中第i个字符之前的k个字符相等，那么匹配仅需要从模式串t中的第k个字符与主串的第i个字符起继续比较[2]。
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<i）与模式串的第一个字符t[1]进行一一比较，若匹配成功则把模式串t[1]移动到s[k]位置继续比较剩余字符，若不成功，则将t串t[i++]处的字符与模式串t的第一个字符进行下一轮的匹配，以此类推，直至结束。 （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<I && j<len（t））
{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
转载注明来源:https://www.xzbu.com/8/view-15251878.htm
