kmp算法用lps数组存储模式串各前缀的最长相等真前后缀长度，构建时用双指针线性推导，匹配时主串指针不回溯，时间复杂度o(n+m)。
用数组实现 KMP 算法，核心在于先用一个整型数组（常称 lps 或 next）存好“部分匹配值”，再用它指导主串扫描时不回溯。关键不是背代码，而是理解数组每个位置代表什么、怎么一步步填出来。
部分匹配表到底存什么
对模式串 pattern，lps[i] 表示子串 pattern[0..i] 中最长相等真前缀与真后缀的长度。注意两点：
- “真”指不能等于整个子串本身（即长度必须
- 前缀从开头起，后缀到结尾止，二者内容完全相同
例如 pattern = "ABABAC"：
- i=0 ("A") → 无真前后缀 → lps[0] = 0
- i=2 ("ABA") → 前缀{"A","AB"}，后缀{"A","BA"} → 共同的是"A" → 长度1 → lps[2] = 1
- i=3 ("ABAB") → 前缀{"A","AB","ABA"}，后缀{"B","AB","BAB"} → 共同的是"AB" → 长度2 → lps[3] = 2
构建 lps 数组的三步逻辑
不用递归、不暴力枚举所有前后缀，靠两个指针在线性时间内完成：
- 设 i 从 1 开始遍历 pattern 索引，len 记录当前已知的最长公共前后缀长度（初始为 0）
- 若 pattern[i] == pattern[len] → 匹配成功，len 加 1，lps[i] = len，i 后移
- 若不等：
→ 若 len > 0，说明前面还有更短的候选前缀，令 len = lps[len−1] 继续比（本质是跳转到上一个可能匹配的位置）
→ 若 len == 0，说明无更短前缀可试，lps[i] = 0，i 后移
实战填充示例：pattern = "ABABC"
逐位推演 lps 数组生成过程：
- i=0：固定 lps[0] = 0，len = 0
- i=1，pattern[1]='B'，pattern[0]='A' ≠ → len=0 → lps[1]=0
- i=2，pattern[2]='A'，pattern[0]='A' = → len=1 → lps[2]=1
- i=3，pattern[3]='B'，pattern[1]='B' = → len=2 → lps[3]=2
- i=4，pattern[4]='C'，pattern[2]='A' ≠；此时 len=2>0 → len = lps[1] = 0；再比 pattern[4] vs pattern[0] → 'C'≠'A' → len=0 → lps[4]=0
最终 lps = [0,0,1,2,0] —— 这就是后续匹配时的跳转依据。
用 lps 数组做匹配的要点
匹配阶段同样用两个指针 i（主串）、j（模式串），遇到失配时：
- 若 j > 0，不重置 j=0，而是 j = lps[j−1]（利用已匹配信息滑动）
- 若 j == 0，说明连首字符都不匹配，i 单独后移
- 每次 pattern[j] == text[i] 时，j 和 i 同步前进；j 达到 pattern 长度即找到匹配
整个过程主串指针 i 从不回退，时间严格 O(n+m)。
