本栏目责任编辑：梁 书
工程应用
Computer KnowIedge and TechnoIogy
电脑知识与技术
第 18 卷第 14 期 (2022 年 5 月)
第 18 卷第 14 期 (2022 年 5 月)
KMP 算法在程序设计竞赛中的应用实践探究
安梓尧，毛玉萃，秦伟勋，郭涵涛
（大连大学，辽宁 大连 ）
摘要：在各类程序设计竞赛中，字符串匹配相关的题目虽然并不常见，但掌握相关的算法却是每个算法学习者必走的路
程。介绍了 算法对实际生活和竞赛的重要性；简述了 算法的原理及其相关的一些算法题目。最后介绍了
算法思想在其他算法中的体现。
关键词：；程序类竞赛；实例
中图分类号： 文献标识码：
文章编号：
开放科学（资源服务）标识码（）：
1 KMP 算法简述
算法全称 算法，是一种在线性时
间内解决字符串匹配问题的算法。在 年由 、
和 三人联合发表。在算法导论第 章里讨论
了 种字符串的匹配算法，分别是 暴力匹配、算
法、有限自动机和 算法
。其中 算法就可以说是有限
自动机的改进版本，即通过在时间复杂度为 的时间
内生成一张前缀表（预处理）以省去计算转移函数 的时间。
下面给出了字符串匹配问题的形式化定义。
）字符串匹配问题的形式化定义
字符串匹配问题的形式化定义如下：假设文本串是一个长
度为 的字符数组 ，模式串是欲与文本串进行匹配的
字符数组 ，其中 且 、，而 、 的元素
都来自有限字母集（即元素都是可打印可输入的）。如果存
在 且 ，那么称模式串 在
文本串 中以有效偏移 出现（即模式串是在文本串的第
到 位置处出现）。现需要找到所有的有效偏移 使得在该
有效偏移下模式串出现在文本串的相应位置。
）算法的原理
对于每模式串 的每个元素 ，都存在一个实数 （），
使得模式串 开头的前 个字符（ ）依次与 前
面的 个字符（ ，这里的第一个字符
最多从 开始（即 ），且 （因为子串总共仅有 个
字符））相同。如果这样的 有多个，则取最大的一个。可以看
到模式串 中每个位置为 的字符都有着这样的 ，在本文里
采用 数组存储。那么得出了 。
如果直接根据 数组的定义求 数组，时间复杂度会
有
，并不是优秀的速度。其实相较于 暴力匹配一次一
次的迭代回溯，算法就在于巧妙地运用了之前已匹配过的
信息并加以运用。所以不妨这样假设，若
均已知，根据 的情况进行分类讨论：
，也就是相等的最长前后缀的长度可以扩
加一位。于是 ； ，令子串
的前 个字符所构成的子串为 ，前面的
个字符构成的子串称为 ，显然地 。
于是在满足“ 的 前缀等于 后缀”
的条件下，可以知道子串 的 一定落于
中，一定落于 中。因为
，所以所求的 就是子串 的相等的最长前后缀
的长度，即 。
进行摊还分析后可以证明此方法构建 数组的时间复
杂度是 。于是实现了以 的时间复杂度构建 数
组并利用 数组进行字符串匹配的算法。
如果对此方法进行进一步理解，可以发现构建 数组这
一步所用的思想其实是动态规划。当把每一个 看成一个
状态，构建的过程可以看成模式串 自己与自己的匹配，也就
是状态的转移。
）算法的现实意义
在现实生活中处处离不开字符串匹配的情景，比如文档的
查找功能或是关键字定位等等，研究相应的算法对小组成员思
维和竞赛水平的锻炼与提升有着巨大的帮助。 算法巧妙
的思想不仅仅可以帮助解决字符串匹配相关的问题，更重要的
在于其可以潜移默化地在解决其他问题时提供新的思路或参
考方向。算法学习环环相扣，研究 算法有着莫大的意义。
）算法的竞赛意义
各类程序设计竞赛里考察字符串匹配的题目相比于其他
算法题目并不是特别常见，但研究此类算法却是小组成员学习
其他字符串相关算法的必备条件之一。程序设计竞赛对计算
收稿日期：2022-02-16
基 金 项 目 ：大 连 大 学 大 学 生 创 新 创 业 训 练 计 划 项 目 ：程 序 设 计 类 竞 赛 中 KMP 算法 处 理 问 题 的 研 究 与 应 用（项目 编 号 ：
S202111258025）
作者简介：安梓尧（2000—），男，云南红河人，本科在读；毛玉萃（1964—），女，江西高安人，副教授，硕士，研究方向为信息系统、算法
和操作系统；秦伟勋（2001—），男，广西桂林人，本科在读；郭涵涛（2002—），男，山西永济人，本科在读学生。
：
：
：
ISSN 1009-3044
Computer KnowIedge and TechnoIogy
电脑知识与技术
，
评论0
最新资源