矩阵矩阵总表：字符串KMP算法详解及C/C++代码实现

1。原因

经过上述，我们知道了暴力匹配算法在时间运算上的缺点。假设字符串 T 的长度为 n，字符串 P 的长度为 m，那么整个算法的时间复杂度为 O(n * m)，对于复杂的现实情况 n >> m >> 2 （即即n远大于m，m远大于常数），这样的计算给计算机带来了沉重的负担。

请想象一个暴力匹配的情况：

给定一个主字符串

T =“AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”（47位）❝同时字符串P =“AAAAAB”（6位）

让我们询问搜寻情况。显然，对于每次搜索，必须先搜索到最后一个字符，然后才能执行下一轮搜索。因此，近似计算可以理解为：O(47 * 6)。为此，很少的数据已经在计算上非常昂贵。

KMP算法是一种改进的模式匹配算法。它由 D.E. 联合出版。Knuth，V.R.Pratt和 J.H. Morris于1977年提出。KMP算法也称为克努特-莫里斯-普拉特运算。 KMP算法与之前的暴力匹配算法最核心的区别在于没有区别。匹配回溯，而是基于整个字符串的偏移，大大减少了回溯带来的缺陷。 KMP算法的时间复杂度可以优化到O(n+m)级别，是对线性级别的二次优化。 。

2。构造下一个表（从-1开始）

对于模式串P，我们需要知道模式串中P的每一位之前是否存在偶数和正偶后缀，并找到最大的正偶后缀。例如，对于模式字符串“ABCABDE”，对于倒数第二个字符，匹配后缀为“AB”，而最后一个字符没有完全匹配的后缀。

PS：什么是后缀和后缀：比如一个字符串“ABCD”，它的前缀可以是“A”、“AB”和“ABC”（即除了自身之外的所有字符）。同样，后缀可以是：“D”“CD”“BCD”

我们需要找到的是每个字符对应的后缀的最大个数，这样模式串P对应的表就称为一对一- 下一张桌子。

因此“ABCABDE”中的下一个表是：-1 0 0 0 1 2 0（字符以空格分隔）

那么我们如何实现代码呢？

对于当前要评估的每个字符，在构建下一个表时，必须根据之前评估的情况向前进行比较（初始值分配为-1，在某些练习中初始值分配为0，有两者没有明显区别），如果后缀+1位置的字符等于前缀+1位置的字符，那么next[i]就是next[i-1]+1 ，如果不相等，则说明无法匹配，所以next[i]=0。

3。 KMP 实现

与暴力匹配非常相似。利用while循环的条件检查，当匹配失败时，只需将失败的模式串P的索引指向下一个表中对应的值，其余的都会匹配。像平常一样线性运行即可。

4。实现代码（仅供参考）