一种基于KMP算法思想的字符串匹配算法的研究与实现

孙娟红

摘要：KMP算法在使用中效率很高，并且在失败匹配之后，不必要重新进行内容字符的匹配，降低了匹配的速度和次数，使得效率大大提高。在本文中，主要是分析了该算法的优点和实现。

关键词：KMP算法思想;字符;串匹配算法;研究;实现

中图分类号：TP311        文献标识码：A

文章编号：1009-3044（2019）26-0196-02

开放科学（资源服务）标识码（OSID）：

当前，我们处于信息化社会，巨大的信息量每天都充斥着人们的生活，不管是在哪个行业和领域中，文本都是承载信息的重要方式，信息的过滤和查找也成了主要的问题。查找字符串并过滤，如果设计不好那么就使得结果无法满足人们的使用要求。所以说，高效率的处理过程就显得尤为关键，随着技术的发展逐渐产生了字符串查找和匹配功能。

1 BF算法

BF算法的理论很简单，就是从内容串C第一个字符起始，到关键字串K的第一个字符，进行挨个比较，在相等的情况下，进进入第二個字符的比较，之后后移，如果在哪个位置失配，那么就需要对关键字串K第一个字符和其内容串中的第二个字符再进行匹配和比较，然后类推。

存在K为关键字串、C为内容串，表达式C=“xyxyy”， K=“xyy”，在C中匹配K。图1即为整个的匹配的过程。在图1中，即体现了BF算法的思想。BF算法的思维十分简单和直接，但是也存在很多的不足，例如内容串定位中错误，并且十分容易进行重复的操作。在失配之后，需要进行二次匹配，在这个过程中，我们需要先采用关键字串第一个字符，将其和内容串第二个字符进行对比，流程可以简化和省略，因为对关键字串进行观察，发现其前边的字符存在不相等性，并且在上轮的对比中，关键字串中的第二个字符于内容串呈现相等的状态，所以说，在关键字串中第一个字符和内容串中第二个字符有着不相等性。在比较的过程中，如果避免这些重复比较过程，那么将会大大提高匹配的效率和水平，于是，KMP算法产生，在很大程度上弥补了BF算法存在的缺陷。

2 KMP模式匹配算法

2.1 算法前瞻

在应用KMP算法的时候，如果匹配失败，不用再重新及西宁匹配和排列，使匹配次数有效减少，促进了效率的提高，这也是其主要的优势所在。该算法主要是依靠move数组进行实现，在move数组中，包含了大量的关键字串。

参考图2，我们进行了例子，将KMP算法和BF算法进行综合的对比，其中就能够看出在KMP算法中，其主要的优势。假定存在有一个内容串C，还有另外一个关键字串K，K=”abcac”，在比较第二个字符的时候，容易产生失配，即C[2]！=K[2]。

根据过去的BF算法，在第二轮开始，需要针对内容串第一个字符，并且针对关键字串第零个字符，在前边标注和说明。利用KMP算法，能够今早了解到K串的特性，就是在开始的两个字符中，存在不相等性，并且在第一轮中可知：C[1]=K[1]，C[0]=K[0]。从上面的表达式中就可以发现，K[0]=C[1]，所以可以省略这一比较环节，直接从k字符开始进行比较，图为第二轮比较详情。

从上面的图3中就可以发现，如果对C[6]-K[4]进行比较的时候，就会发生配比失效的情况。而按照KMP思想只需要比较C[6]与K[1]就可以，如下图所示。

从上述分析可知，在所有的环节中产生了三次重新匹配，并且匹配成功，并得出了有效的结论，提高了匹配的效率和水平。在以上的例子中，对方法只是进行了大体的概括和分析，其方法的本质该是什么，怎么样能保障思路精确，如果实现最后代码等等，这些问题都要进行进一步研究并解决。

2.2 算法思想

通过上述的研究得知，实际在开展匹配的时候，当出现失败的情况，那么就只针对关键字串K，追溯其初始位置，而在内容串中，其比较位置是往后进行，不会存在重复。

我们能够得出：在使用KMP算法的时候，如果匹配失败仍然可以了解关键字串的位置，并且能够在失配位置进行寻找和定位，然后再进行比较，在整个算法过程中，对关键字串的重新定位和比较十分重要，并且这和内容串的关系很小，几乎不存在关系。

在KMP算法使用中，最主要的是其move数组，对move数组的有效利用，能够确保在失配前提下，进行关键字串的移动，并选择移动的范围和位数，从而减少匹配时间。应用KMP思想，就需要充分考虑怎么做好移位的工作。可以通过move数组，当在内容串的时候，匹配的是关键字的串字符，就需要同时移动两者下标。当匹配失败的情况发生时，那么需要move数组，实现关键字串的有效移动。

2.3 求解move数组

move数组概念定义：对于键字串K，如果和内容串C在匹配过程中，有n个字符完成匹配，那么这些同时是在关键字串K中的前n个字符，对于该子串，我们利用tmp进行综合分析：

串tmp前后是否出现重复内容，可以表示为单个字符重复，重复越多越好，只对重复最多的时候进行记录，对于该长度，在进行重新匹配的过程中，无须进行长度的重新测量，并且需要详细记录重复的间隔距离。当这一距离出现配比失败的时候，可以通过回溯长度的方式为关键字串K。所以，在对n下方匹配长度的时候，能够有效提升效率。

2.4 move数组求解算法

代码思路比较简单，其根本就是对关键字串和内容串进行的匹配，直到长度j，并得出匹配内容tmp，之后对其进行有效拆分，分为两大部分，分别是前缀与后缀，而长度需要确保后缀更长。所以，对于后缀中是否出现前缀要密切进行观察，在前缀和后缀中，可以找出的重复最长值放在move[j]中。Move最开始的数据都是0，表示在关键字串中，已经重新到头部而且没有发生偏移。

3 在项目中算法的应用和实现分析

3.1 KMP模式匹配算法

就函数功能来看，是在KMP思想之下，进行关键字串的确定和查找。即：匹配长度应用的计数器是matchlen，并且在完成匹配字符之后的（37行）、（38行），对（43行）进行计数。当在（50行）出现失配的情况时，就表示长度为0，也就是在第一个字符中，就产生了不匹配，要对内容串指针进行后移，到（52行）。在（53行）中matchlen已经记录了完成匹配的字符，而move[matchlen]是指完成匹配matchlen个字符后前缀和后缀的出现状态，在下次进行比较的时候，就需要定位关键字串，之后就可以进行move[matchlen]个长度的偏移。这里指的长度为跳过的长度，无法进行重复对比，单也属于匹配长度范畴，所以53行存在赋值。

4 结束语

综上所述，本文通过研究BF算法，分析了KMP的算法思想，并对其应用优势进行了总结分析。而且，对于KMP算法中的实现对策进行了阐述，进一步解答了move数组求解。当字符集较大时，针对BF算法和KMP算法进行对比和分析，利用KMP算法，不管是在精确度还是效率上，都远远强于BF算法。基于这一情况，在对KMP算法应用的时候，一定要充分考虑实际情况，尽可能提高匹配效率，扩大应用范围。

通过分析算法可以得知，能够通过比较各个算法的效率和過程发现不同算法的特点和优势，从而能够进行自己算法的有效选择，掌握能够遵循的主要方式，在日常的学习和生活中进行广泛的应用。

参考文献：

[1] 余飞.模式匹配算法的分析与研究[J].电脑知识与技术，2018，14（10）：251-252.

[2] 韦安垒，李开科，张榆.一种快速单模式匹配算法的设计与实现[J].网络空间安全，2018，9（1）：86-92.

[3] 吴同，李思其，杨卫军，等.基于KMP算法的云存储数据取证方法研究[J].信息网络安全，2017（12）：36-39.

[4] 王晓波.基于KMP算法Next数组的分析与优化[J].电子世界，2017（20）：196，198.

[5] 任平红，陈矗.数据结构中模式匹配算法的教学方法探讨[J].电脑知识与技术，2017，13（27）：173-174.

[6] 蔡婷，杨卫帅.一种改进的字符串模式匹配算法[J].物联网技术，2017，7（7）：89-91，95.

【通联编辑：唐一东】