KMP算法在程序设计竞赛中的应用实践探究

2022-07-05安梓尧毛玉萃秦伟勋郭涵涛

电脑知识与技术 2022年14期

关键词：实例

安梓尧毛玉萃秦伟勋郭涵涛

摘要：在各类程序设计竞赛中，字符串匹配相关的题目虽然并不常见，但掌握相关的算法却是每個算法学习者必走的路程。介绍了KMP算法对实际生活和竞赛的重要性;简述了KMP算法的原理及其相关的一些算法题目。最后介绍了KMP算法思想在其他算法中的体现。

关键词：KMP;程序类竞赛;实例

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

文章编号：1009-3044（2022）14-0080-03

1 KMP算法简述

KMP 算法全称Knuth-Morris-Pratt算法，是一种在线性时间内解决字符串匹配问题的算法。在1977年由D.E.Knuth、J.H.Morris和V.R.Pratt三人联合发表。在算法导论第32章里讨论了4种字符串的匹配算法，分别是BF暴力匹配、Rabin-Karp算法、有限自动机和KMP算法[1]。其中KMP算法就可以说是有限自动机（DFA）的改进版本，即通过在时间复杂度为O（m）的时间内生成一张前缀表（预处理）以省去计算转移函数δ的时间。下面给出了字符串匹配问题的形式化定义。

1）字符串匹配问题的形式化定义[1]

字符串匹配问题的形式化定义如下：假设文本串是一个长度为n的字符数组txt[1 … n]，模式串是欲与文本串进行匹配的字符数组pat[1 … m]，其中m≤n且m≠∞、n≠∞，而txt、pat的元素都来自有限字母集∑（即元素都是可打印可输入的）。如果存在0≤s≤n-m且txt[1+s … m+s]=pat[1 … m]，那么称模式串pat在文本串txt中以有效偏移s出现（即模式串是在文本串的第s+1到s+m位置处出现）。现需要找到所有的有效偏移s使得在该有效偏移下模式串出现在文本串的相应位置。

2）KMP算法的原理

对于每模式串pat的每个元素pi，都存在一个实数k（k≥0），使得模式串pat开头的前k个字符（p0， p1， … pk-1）依次与pi前面的k个字符（pi-k ， pi-k+1 ， … pi-1 ，这里的第一个字符pi-k最多从p1开始（即i-k≥1），且k<i+1（因为子串总共仅有i+1个字符））相同。如果这样的k有多个，则取最大的一个。可以看到模式串pat中每个位置为i的字符都有着这样的k，在本文里采用next数组存储。那么得出了 next[i]=max{k}。

如果直接根据next数组的定义求next数组，时间复杂度会有Ο（m2），并不是优秀的速度。其实相较于BF暴力匹配一次一次的迭代回溯，KMP算法就在于巧妙地运用了之前已匹配过的信息并加以运用。所以不妨这样假设，若next[0]， next[1]， … next[i-1]均已知，根据p[i]的情况进行分类讨论：

p[i] = p[next[i-1]]，也就是相等的最长前后缀的长度可以扩加一位。于是next[i] = next[i-1]+1;p[i] ≠ p[next[i-1]]，令子串p[0] … p[i]的前next[i]个字符所构成的子串为prefix[i]，p[i]前面的next[i]个字符构成的子串称为suffix[i]，显然地prefix[i]=suffix[i]。于是在满足“p[0] … p[i-1]的next[i-1]前缀等于next[i-1]后缀”的条件下，可以知道子串p[0] … p[i]的prefix[i]一定落于prefix[i-1]中，suffix[i]一定落于suffix[i-1]中。因为prefix[i-1]=suffix[i-1]，所以所求的next[i]就是子串prefix[i-1]的相等的最长前后缀的长度，即next[i]=next[next[i-1]-1]。

进行摊还分析后可以证明此方法构建next数组的时间复杂度是Ο（m）。于是实现了以Ο（m+n）的时间复杂度构建next数组并利用next数组进行字符串匹配的算法。

如果对此方法进行进一步理解，可以发现构建next数组这一步所用的思想其实是动态规划。当把每一个next[i]看成一个状态，构建的过程可以看成模式串pat自己与自己的匹配，也就是状态的转移。

3）KMP算法的现实意义

在现实生活中处处离不开字符串匹配的情景，比如文档的查找功能或是关键字定位等等，研究相应的算法对小组成员思维和竞赛水平的锻炼与提升有着巨大的帮助。KMP算法巧妙的思想不仅仅可以帮助解决字符串匹配相关的问题，更重要的在于其可以潜移默化地在解决其他问题时提供新的思路或参考方向。算法学习环环相扣，研究KMP算法有着莫大的意义。

4）KMP算法的竞赛意义

各类程序设计竞赛里考察字符串匹配的题目相比于其他算法题目并不是特别常见，但研究此类算法却是小组成员学习其他字符串相关算法的必备条件之一。程序设计竞赛对计算机相关专业的学生来说具有很大的帮助，考验着学生的耐心、专注度、逻辑水平等。

5）KMP算法的C++代码

KMP算法的用C++实现的代码如图1所示。

2 KMP算法在程序设计竞赛中运用

1）Oulipo问题[2]

题目：求字符串W在字符串T中出现了几次？

输入：标准输入的第一行包含一个整数n，表示有n组数据。

接下来的每两行里第一行包含了一个字符串W {'A'， 'B'， 'C' … 'Z'}，下一行包含一个字符串T {'A'， 'B'， 'C' … 'Z'}

输出：对于每组测试样例，输出字符串W在字符串T中出现了几次。

样例输入：

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

样例输出：

分析：题目要求是求出W在T中出现的次数，很明显，KMP就是解决这种问题的。图2给出主要的算法代码。需要注意的是第九行（j = next[j]），如不做此修改则会超时。

2）Seek the Name， Seek the Fame问题[3]

题目：有一位法师道法很强，人们总是为他们新出生的宝宝慕名而来，以求得法师为他们的孩子取吉利的名字。时间久了法师自然也就乏了，于是他想出了一个对策：

首先，把宝宝父母亲的名字加起来拼凑成一个新的字符串S;接着，在S的所有公共前后缀子串里挑一个给宝宝起名。比如：父亲的名字是“ala”，母亲的名字是“la”。它们拼凑成的字符串S为“alala”。其中S的所有前缀为：“a”“al”“ala”“alal”“alala”;字符串S的所有后缀是：“a”“la”“ala”“lala”“alala”。所以它们的公共前后缀是：“a”“ala”“alala”。现有一个字符串S，需要帮助法师编写一个程序以计算所有公共前后缀的长度。

输入：输入含有多组测试用例，每组用例均给出字符串S。注意字符串S只由小写字母构成。

输出：对于每组测试样例，按从小到大输出字符串S的所有公共前后缀的长度，代表着宝宝可能名字的长度。

样例输入：

ababcabab ababcabab

aaaaa

样例输出：

2 4 9 18

1 2 3 4 5

分析：要想得出公共前后缀的长度首先就需要求出字符串S的所有公共前后缀。这里就运用到了KMP中next数组的思想。具体地，因为next[i]数组的含义是p[1 … i]的最长公共前后缀，所以可以先求出字符串S的最长公共前后缀，那接下来的公共前后缀就只会出现在这最长的公共前后缀里了。只要按照这个思路一直循环下去直到next[i] = 0时就说明找到所有的公共前后缀。例如样例一的ababcababababcabab，它的最长公共前后缀为ababcabab（即在next数组里next[18] = 9）。因为其他的公共前后缀只会比“ababcabab”短，所以按动态规划的思想一样把眼光专注于这个子串，它的最长公共前后缀为next[9] = 4;依次循环，next[4] = 2;next[2] = 0（也就是子串“ab”已经没有公共前后缀了）。于是求出了所有的公共前后缀。它们的长度在计算保存一下即可。其主要代码如图3所示。

3）Power Strings问题[4]

题目：现有两个字符串x， y，是这样定义：x+y代表着将两个字符串拼接在一起。比如，a=“abc”，b=“gcg”，那么a+b = “abcgcg”。同理[ i=0nxi]代表着n个字符串拼接在一起;n*x代表着n个相同的字符串x拼接在一起;0*x=“ ”代表着空字符串; （n+1） * x = x + x * n。

输入：输入多组测试用例，每组包含了一串可打印字符的字符串x（其长度为1-1000000）。最后一行为以“.”标识结束输入。（本题有很大输入，应使用scanf代替cin）

输出：对于每组输入，对于满足x = a*n的字符串中数量最多的那个字符串a，你需要给出有多少个a拼接成了x。

样例输入：

abcd

aaaa

ababab

样例输出：

分析：在KMP算法中，next表示模式串pat的最长公共前后綴，也就是p[0] … p[next[i]]完全等于p[n-next[i]] … p[n]，所以若i%（i-next[i]） = 0，则可以说明存在着重复的连续子串，其长度为n-next[n]。其主要部分代码如图4所示。

4）重复的子字符串问题[5]

题目：给出一个长度大于0的字符串s，问这个字符串s是否能由若干个它的子串si来构成。

输入：一个字符串s

输出：若能由若干个子串构成则输出true，否则输出false

样例示范：

样例1：

输入：abcdabcd

输出：true

样例2：

输入：abaabaaba

输出：true

样例3：

输入：abababa

输出：false

解析：题目要求是找出一个s的子串si，来判断能否由若干个si组成一个s。可以很容易地想到，如果可以从s中穷举出可能出现的所有子串si，每当枚举出一个si就使用这个si去不断拼接自己，尝试能否由k（k>1）个si组成一个s。

有了这个思路，可以计算一下时间复杂度。如果枚举出一个字符串中的所有子串，是需要两层for循环的，时间复杂度为O（n2）。有了枚举出来的子串si就可以去进行拼接操作，进行k次拼接，得到一个与s长度相等的字符串，就可以进行字符串匹配比较了。拼接和比较相等的时间复杂度均为O（n）。

考虑优化不必要枚举出所有的字符串，观察样例2，若枚举出的一个子串是s.substr（3，3）。进行拼接时需要去把字符串s的前三位进行填充。若枚举字符串只枚举s.substr（1，i∈[0， s.length（））即可。枚举时可以做进一步的优化的，假设枚举的字符串si长度为si.length（），若s.length（）%si.length（）！=0则必定不能够拼接出s。

设子串si为能够拼出s的最短字符串，假设k个si能组成一个s。讨论k的范围，若k == 2，则两个si分别一个组成s的前缀一个组成s的后缀。若k == 3，则可以由四个si平别组成s的前后缀，中间会重复一个si。若k == 4，则可以在k == 2的基础上将两个si合并成一个sj，组成了最终结果。k>= 4时以此类推。

经过上面的分析，合法的子串si（不一定最短）必定会组成s的前缀和后缀，涉及前缀子串和后缀子串，就不难想到之前说过的KMP算法了。在求next数组时，就需要求最长的相等前后缀。利用这个性质，就可以快速来解一道题了。当计算出KMP中的next数组的最长相等前后缀时，若存在k个si能组成s，则next[s.length（）-1]的值必定为s.length（）-si.length（）（其中si为满足要求的最小子串长度）。因而可以用s.length（）%si.length（） == 0来判断是否存在符合題目要求的si。其实现的主要部分代码如图5所示。

3 KMP算法在其他算法中的运用

KMP算法还在许多其他算法中得以应用，在这里简单介绍在 Border树中的应用。

Boeder树也叫作失配树，就是运用KMP算法求失配数组时让点i的父亲为next[i]。通过next数组把0 … n个点连成一棵树。这种树有性质主要有：

1）每一个点的所有祖先一定是它自身的border。

2）任意两个点的任意公共祖先是它们的共同的border。

3）传递性，若串a是串b的border，串b是串c的border，那么串a是串c的border。例如“aba”是“ababa”的border，“ababa”是“ababababa”的border。依据传递性，“aba”是“ababababa”没有祖先关系的两个点i，j没有border。

4）借助Border树的这些性质，可以衍生出各种应用，例如：求公共前缀串，和border的数量等。

4 结束语

算法的研究与学习总是没有尽头的，对KMP算法本质的理解同样如此。在开展研究的过程中，作者彼此间互相提供丰富的建议与思路。作者非常期望这一简单但很有意义的工作可以激发本领域更多同行研究人员在本方向上开展更为详尽深入的研究。

参考文献：

[1] Cormen T H.算法导论[M].殷建平，译.北京：机械工业出版社，2013.

[2] Oulipo[EB/OL].[ 2021-10-14].http：//poj.org/problem？id=3461.