数据结构中KMP算法是什么?

来源：千锋教育

发布人：xqq

时间： 2023-10-19 14:22:04

一、数据结构中KMP算法

KMP算法介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法是在 BF 算法基础上改进得到的算法。学习 BF 算法我们知道，该算法的实现过程就是 “傻瓜式” 地用模式串（假定为子串的串）与主串中的字符一一匹配，匹配不成功则返回到上一次与主串匹配的下一位字符进行匹配，算法执行效率不高。

KMP算法的解决题型

KMP算法是在数据结构中两个字符串相互匹配衍生出来的算法。KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。例如，对主串 A（“ABCABCE”）和模式串 B（“ABCE”）进行模式匹配，如果人为去判断，仅需匹配两次。虽然在以上字符较少的串中人为匹配很容易，但是让计算机来匹配就相对慢一些，但是当字符串中的字符非常多的时候，就不可能人为去匹配。所以打铁还需自身硬，我们把这种枯燥的事以一定的算法交给计算机处理。

KMP算法相比BF算法的改进

每当一趟匹配过程中出现字符比较不等时，无需回溯i指针（即无需将i指针完全退回至i-j+1），而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

需要解决的问题：当主串中的第i个字符与模式中第j个字符比较不相等时，主串中第i个字符（i指针不回溯）应与模式中哪个字符再比较？—-假设从主串中第i个字符与模式中的第k个字符再进行比较

它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！

　　这种信息就是对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里名列前茅个字符 t j-k 非常多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }。

延伸阅读：

二、KMP算法的时间复杂度

主要由两部分组成：预处理部分和匹配部分。

预处理部分：在这一步，算法计算模式串的最长公共前缀和后缀（也称为部分匹配表或失效函数）。这一步的时间复杂度为O(m)，因为它遍历了整个模式串。匹配部分：在这一步，算法在目标文本中查找模式串。在最坏的情况下，这一步的时间复杂度为O(n)。这是因为算法在进行比较时，可以根据失效函数跳过不匹配的字符，因此，它不需要对每个字符进行逐一比较。

综合考虑这两部分，KMP算法的总时间复杂度为O(m+n)。与朴素的字符串匹配算法相比（其时间复杂度为O(mn)），KMP算法具有更高的效率，尤其在处理大量数据时。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。