KMP算法的优化——串模式匹配算法

文章目录

• KMP（Knuth Morris Pratt）算法
• • next函数
  • KMP具体代码
  • next函数改进

KMP（Knuth Morris Pratt）算法

KMP算法是对字符串匹配算法的一种优化方案，在计算机科学领域由D.E.Knuth、J.H.Morris和V.R.Pratt三人命名。因此通常称为克努特-莫里斯-普拉特（简称KMP）算法。其核心在于通过失败匹配的信息来优化后续匹配过程，并最大限度地减少模式串与主串的比较次数。具体而言，则通过next()函数来实现这一功能。该算法的时间复杂度为O(m+n)。

KMP算法是一种能在主串长度为m、模式串长度为n时实现线性时间复杂度的字符串模式匹配方法。其改进的核心在于：当在每一轮扫描过程中一旦发现字符比较不一致时，在已有的部分匹配信息基础上将模式向右移动至最长可能的位置后继续与主串进行比对。

例：
主 串 : S=a c a c b a c b a a b c a
模式串:T=a c b a b

如图所示，在匹配过程中：

• 第一轮比较失败