KMP算法介绍

简介

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，称之为Knuth-Morris-Pratt算法，简称KMP算法。该算法与Brute-Force算法相比有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

实现

1、从模式串t中提取加速匹配的信息

具体来说就是求next数组，next数组的定义如下：

$$next[j]=\begin{cases} -1 & 当j=0时\\MAX\{k \,|\, 0<k<j {\ } and {\ } "t_0t_1\cdot \cdot \cdot t_{k-1}"="t_{j-k}t_{j-k+1}\cdot \cdot \cdot t_{j-1}"\}&前后缀相等时\\0 &其它情况\end{cases}$$

KMP算法介绍

原文：https://www.cnblogs.com/lfri/p/10339410.html