前言
KMP 算法是由 Knuth、Morris、Pratt 三位学者共同提出的字符串匹配高效算法，核心解决了传统暴力匹配算法中'主串指针回溯'的问题，将时间复杂度优化到线性级别。
一、算法概述
1. 解决的问题
字符串匹配问题：给定主串 S 和模式串 P，判断模式串 P 是否是主串 S 的子串，若存在，返回其在主串中首次出现的起始索引；若不存在，返回 -1。
2. 传统暴力匹配的问题
暴力匹配（BF 算法）的思路是：主串指针 i 和模式串指针 j 从起始位置开始逐一匹配，若 S[i] != P[j]，则 i 回溯到 i-j+1，j 重置为 0，重新匹配。
- 问题核心：主串指针的回溯导致大量重复比较，最坏时间复杂度为 O(n*m)（n 为主串长度，m 为模式串长度）。
- 例子：主串 S = 'AAAAAAB'，模式串 P = 'AAAB'，暴力匹配会在第 4 位匹配失败后反复回溯，效率极低。
动态演示
3. KMP 算法的核心改进
KMP 算法通过预处理模式串 P，生成 next 数组，让主串指针 i 永不回溯，仅通过模式串指针 j 的回退实现匹配，将时间复杂度优化到 O(n+m)。
- 核心思想：当 S[i] != P[j] 时，利用已匹配的前缀信息，让 j 回退到当前位置的最长公共前后缀的后缀末尾下一位，而非直接重置为 0，避免重复比较。
二、算法核心原理
理解 KMP 的关键，先掌握最长公共前后缀这个核心概念，再理解 next 数组的作用。
关键概念：最长公共前后缀（真前后缀）
对于模式串的子串 P[0…j]，真前缀是指不包含最后一个字符的所有前缀，真后缀是指不包含第一个字符的所有后缀；最长公共前后缀就是真前缀和真后缀中长度最大的相等子串。
- 注意：真前后缀不能是子串本身，否则无意义
- 若子串无相等的真前后缀，最长公共前后缀长度为 0（如 P[0…1]=AB）。
实例：字符串 P = 'abcab'，前缀有'a','ab','abc','abca', 后缀有'b','ab','cab','bcab'。最长公共前后缀字符串就是'ab'，长度为 2。
对于字符串"aaaaa"，求最长公共前后缀长度的过程如下:
对于字符串"abacb"，求最长公共前后缀长度的过程如下：
