什么是 KMP 算法？

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主文本串 S 中查找一个模式串 P 的出现位置。它的核心优势在于，当匹配过程中发生不一致时，它能利用已经匹配过的信息，跳过一些不必要的比较，从而避免了暴力匹配中的指针回溯，将时间复杂度优化到线性 O(n+m)。

核心思想：next 数组

KMP 算法的精髓在于一个预处理过的 next 数组（有时也叫 lps 数组，表示最长公共前后缀 Longest Proper Prefix which is also Suffix）。next[i] 存储的是模式串 P 的子串 P[0...i] 中，最长的相等的前缀和后缀的长度。