KMP算法

KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，它通过避免回溯主串指针来实现O(n+m)的时间复杂度。要深入理解KMP算法，需要掌握其核心思想——部分匹配表（Pi数组）和匹配过程中的智能回退机制。

1. 核心思想：利用已匹配信息避免重复比较

传统暴力匹配算法在每次失败时需要回溯主串指针，导致大量重复比较。KMP算法通过预处理模式串，构建一个"部分匹配表"（Pi数组），利用这个表在匹配失败时只回退模式串指针，主串指针永不回溯。

2. 部分匹配表（Pi数组）

Pi数组存储了模式串每个位置的最长公共前缀后缀长度（Longest Proper Prefix which is also Suffix）。

定义：

pi[i] = 子串needle[0..i]中，既是真前缀（不包含自身）又是真后缀（不包含自身）的最长子串长度。

示例（模式串"ababc"）：

子串	真前缀	真后缀	公共部分	pi[i]
a	无	无	无	0
ab	[a]	[b]	无	0
aba	[a, ab]	[ba, a]	"a"	1
abab	[a,ab,aba]	[bab,ab,b]	"ab"	2
ababc	[a,ab,aba,abab]	[babc,abc,bc,c]	无	0

Pi数组结果：[0, 0, 1, 2, 0]

Pi数组构建过程：

vector<int> pi(m, 0);  // 初始化全0
for (int i = 1, j = 0; i < m; i++) {
    while (j > 0 && needle[i] != needle[j])
        j = pi[j-1];  // 回退到前一个匹配位置
    
    if (needle[i] == needle[j]) 
        j++;  // 匹配时扩展公共长度
    
    pi[i] = j;  // 记录当前位置的LPS
}

3. 匹配过程：智能回退机制

当匹配失败时，利用Pi值决定模式串指针回退的位置，主串指针不回溯。

for (int i = 0, j = 0; i < n; i++) {
    while (j > 0 && haystack[i] != needle[j])
        j = pi[j-1];  // 关键：回退模式串指针
    
    if (haystack[i] == needle[j]) 
        j++;
    
    if (j == m)  // 完全匹配
        return i - m + 1;
}

匹配示例（主串："abababc"，模式串："ababc"）：

步骤1: [a]bababc ←→ [a]babc  匹配，j=1
步骤2: a[b]ababc ←→ a[b]abc  匹配，j=2
步骤3: ab[a]babc ←→ ab[a]bc  匹配，j=3
步骤4: aba[b]abc ←→ aba[b]c  匹配，j=4
步骤5: abab[a]bc ←→ abab[c]  不匹配 → 回退 j = pi[3] = 2
         ▲(主串指针保持不动)
         ab[a]bc  ←→ 回退后重新比较
步骤6: abab[a]bc ←→ ab[a]bc  匹配，j=3
步骤7: ababa[b]c ←→ aba[b]c  不匹配 → 回退 j = pi[2] = 1
步骤8: ababa[b]c ←→ a[b]c    不匹配 → 回退 j = pi[0] = 0
步骤9: ababa[b]c ←→ [a]bc    不匹配 → i继续前进
...