算法（④KMP）
KMP 算法的核心原理
利用模式串自身的“对称性”进行跳跃。
这个“对称性”就是我们之前提到的最长公共前后缀。
当匹配失败时，KMP 算法不会从头再来，而是会利用已经匹配成功的部分信息，直接将模式串移动到下一个最可能匹配的位置。
好的，我们来详细计算 ABABABC 这个模式串的部分匹配表（LPS 表）。
什么是部分匹配表？
部分匹配表记录了模式串中，以每个字符结尾的子串的最长公共前后缀的长度。这个表就是 KMP 算法的“导航图”。
计算过程
我们从左到右，一步步计算每个位置的值。
| 模式串 (P) | A | B | A | B | A | B | C |
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 子串 | A | AB | ABA | ABAB | ABABA | ABABAB | ABABABC |
| LPS 值 | ? | ? | ? | ? | ? | ? | ? |
导出到 Google 表格
1. 子串 A (索引 0)
前缀：空
后缀：空
最长公共前后缀长度：0
2. 子串 AB (索引 1)
前缀：
A后缀：
B没有公共部分。
最长公共前后缀长度：0
3. 子串 ABA (索引 2)
前缀：
A,AB后缀：
A,BA最长公共部分是
A。最长公共前后缀长度：1
4. 子串 ABAB (索引 3)
前缀：
A,AB,ABA后缀：
B,AB,BAB最长公共部分是
AB。最长公共前后缀长度：2
5. 子串 ABABA (索引 4)
前缀：
A,AB,ABA,ABAB后缀：
A,BA,ABA,BABA最长公共部分是
ABA。最长公共前后缀长度：3
6. 子串 ABABAB (索引 5)
前缀：
A,AB,ABA,ABAB,ABABA后缀：
B,AB,BAB,ABAB,BABAB最长公共部分是
ABAB。最长公共前后缀长度：4
7. 子串 ABABABC (索引 6)
前缀：
A,AB,ABA,ABAB,ABABA,ABABAB后缀：
C,BC,ABC,BABC,ABABC,BABABC没有公共部分。
最长公共前后缀长度：0
最终的部分匹配表
经过计算，我们得到了完整的 LPS 表：
| 模式串 (P) | A | B | A | B | A | B | C |
| LPS 值 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |