KMP 算法

学习数据结构与算法
2022-08-27 19:15 · 阅读时长4分钟

KMP 算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的,KMP 算法的时间复杂度 O (m+n)。

相同前后缀

KMP 算法之所以能够快速匹配,主要是因为在迭代过程中并不是逐个查找,而是根据模式串的最长相同前后缀表进行跳跃查找。这里的相同前后缀指的是字符串中前缀和后缀相同的子串,不包括整个字符串

示例 1:“aba”,“a” 既是 “aba” 的前缀,也是 “aba” 的后缀,所以 “a” 就是 “aba” 的相同前后缀。
示例 2:“ababa”,“a” 是 “ababa” 的相同前后缀,“aba” 也是 “ababa” 的相同前后缀。

下面演示 “abacabad” 的最长相同前后缀表是如何得到的。

加载中...
查找演示

看看 KMP 算法如何使用最长相同前后缀表进行查找。

字符串,“abacabaabacabad”
模式串,“abacabad”
匹配图解
加载中...

字符串和模式串前 7 个字符都能匹配上,当 i=7,j=7 时,匹配失败。如果是暴力查找,那么就需要让 i=1,j=0,然后重新开始匹配,如下:

加载中...

如果是 KMP 算法会是怎样呢?
直接将模式串已成功匹配的前缀 “aba” 和字符串已成功匹配的 “aba” 对齐,让 i=7,j=3,然后继续匹配。如下:

加载中...

因为只有模式串成功匹配的子串 “abacaba” 中的某个前缀和字符串中已经匹配成功的子串 “abacaba” 中的某个后缀相同,后续的比较才有意义,而且只有取最长的相同前后缀才不会遗漏可能的匹配,而 “aba” 就是 “abacaba” 的最长相同前后缀。

i=7,j=3 匹配失败,所以继续将模式串已成功匹配的前缀 “a” 和字符串已成功匹配的 “a” 对齐,让 i=7,j=1,然后继续匹配。如下:

加载中...

i=7,j=1 匹配失败,因为已成功匹配的子串没有相同前后缀,所以将模式串整体后移和字符串未匹配成功的字符对齐,让 i=7,j=0,然后继续匹配下去。如下:

加载中...

最终匹配完成,从第一第二阶段来看,KMP 算法比暴力查找算法少了很多无用的循环,所以效率比较比暴力查找自然快多了。注:KMP 算法时间复杂度是 O (m+n),暴力查找是 O (m*n)。

算法实现
加载中...
KMP算法字符串匹配