KMP算法（字符串匹配）
KMP算法（Knuth-Morris-Pratt Algorithm）是一种高效的字符串匹配算法。它的核心思想是，当主串与模式串进行匹配过程中发生字符不匹配时，利用模式串本身的信息，避免主串指针的回溯，从而将匹配的时间复杂度优化到O(n+m)，其中n是主串长度，m是模式串长度。
1. 问题背景与暴力匹配的不足
字符串匹配问题：给定一个主串（文本串）T 和一个模式串 P，我们需要在主串 T 中找出模式串 P 首次出现的起始位置。
最直观的方法是暴力匹配（Brute-Force）：
- 将模式串
P与主串T的每一个可能的起始位置进行对齐比较。 - 从对齐位置开始，逐个字符比较
P和T。 - 如果遇到不匹配的字符，则将模式串
P整体向右移动一位，重新从P的开头进行比较。
暴力匹配示例：
主串 T: "ABABDABACDABABCABAB"
模式串 P: "ABABCABAB"
第一轮比较（从T[0]开始）：
T: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B
^ 不匹配发生在 P[4]='C' 与 T[4]='D'
按照暴力匹配，下一步是将P右移一位，从T[1]开始重新比较。这导致了大量的重复比较，因为T的指针（索引）发生了回溯。最坏情况下时间复杂度为O(n*m)。
2. KMP算法的核心思想：利用已知信息避免回溯
KMP算法的关键在于：当发生不匹配时，模式串 P 应该向右滑动多远？并且主串 T 的指针不需要回溯。
观察上面的不匹配点：
不匹配发生在 P[4] = 'C' 和 T[4] = 'D'。
在发生不匹配之前，我们已经成功匹配了 "ABAB" 这四个字符。
KMP算法会问：在已经匹配的字符串 "ABAB" 中，是否存在一个真前缀（不等于字符串本身的前缀）同时也是一个真后缀？
- "ABAB" 的前缀有： "A", "AB", "ABA"
- "ABAB" 的后缀有： "B", "AB", "BAB"
- 共同的真前缀和真后缀是："AB"（长度=2）
这个最长的公共真前后缀的长度（这里是2）至关重要。它告诉我们，我们可以直接将模式串 P 向右移动，使得这个公共后缀（"AB"）与主串中刚刚匹配成功的对应前缀（"AB"）对齐。这样，我们不需要从T[1]开始比较，而是从刚刚发生不匹配的位置T[4]继续与P[2]（因为公共前后缀长度是2，所以下一个要比较的是P[2]）开始比较。
滑动过程图解：
发生不匹配时：
T: ... A B A B D ...
P: A B A B C ... (不匹配发生在P[4]和T[4])
^^^^^ 已匹配部分 "ABAB"
| |
前缀 后缀 (最长的公共前后缀是"AB"，长度为2)
滑动后，利用公共前后缀对齐：
T: ... A B A B D ...
P: A B A B C ... (现在从P[2]开始和T[4]比较)
^
下一个比较位置
主串指针 i 保持在位置4不动，模式串指针 j 从4回退到2。这样我们就避免了主串指针的回溯。
3. 部分匹配表（Next数组）的构建
为了在匹配时能快速知道指针 j 应该回退到哪里，我们需要预先为模式串 P 计算一个重要的数组——部分匹配表（Partial Match Table），也常被称为 next数组。
next数组的定义：
next[j] 表示模式串 P 的子串 P[0..j]（即从开头到第j个字符的子串）中，最长的、相等的真前缀和真后缀的长度。
计算next数组的步骤（递推法）：
我们使用两个指针：i 和 j。
i：指向当前子串的末尾（用于遍历P，从1到m-1）。j：指向上一个子串的最长公共前后缀的长度（也指向下一个待匹配的前缀位置）。- 初始化：
next[0] = 0（单个字符没有真前后缀），j = 0,i = 1。
然后开始遍历 i 从1到m-1：
- 如果
P[i] == P[j]：- 说明我们找到了一个更长的公共前后缀。长度是
j+1。 - 所以，
next[i] = j + 1。 - 然后同时后移
i和j（i++,j++）。
- 说明我们找到了一个更长的公共前后缀。长度是
- 如果
P[i] != P[j]：- 情况变得复杂。我们不能直接延长公共前后缀。
- 我们需要回退指针
j。j应该回退到哪里？答案是回退到next[j-1]。 - 理解回退：我们希望找到在
P[0..j]这个已匹配前缀中，一个更短的公共前后缀，然后尝试用P[i]和这个更短前缀的下一个字符进行比较。 - 如果
j已经大于0，则令j = next[j-1]，然后重新比较P[i]和P[j]。 - 如果
j已经回退到0，并且P[i]仍然不等于P[0]，那么说明在P[0..i]中不存在公共前后缀，设置next[i] = 0，然后i++。
以模式串 P = "ABABCABAB" 为例，计算next数组：
P: A B A B C A B A B
索引:0 1 2 3 4 5 6 7 8
next[0] = 0(初始化)i=1, j=0: P[1]='B' != P[0]='A', 且j=0, 所以next[1]=0, i++ -> i=2i=2, j=0: P[2]='A' == P[0]='A', 所以next[2] = j+1 = 1, 然后 i++, j++ -> i=3, j=1i=3, j=1: P[3]='B' == P[1]='B', 所以next[3] = j+1 = 2, 然后 i++, j++ -> i=4, j=2i=4, j=2: P[4]='C' != P[2]='A'。发生不匹配，j回退。j = next[j-1] = next[1] = 0。- 现在
j=0, 比较 P[4]='C' 和 P[0]='A'，仍然不相等。且j=0，所以next[4]=0, i++ -> i=5
- 现在
i=5, j=0: P[5]='A' == P[0]='A', 所以next[5] = j+1 = 1, 然后 i++, j++ -> i=6, j=1i=6, j=1: P[6]='B' == P[1]='B', 所以next[6] = j+1 = 2, 然后 i++, j++ -> i=7, j=2i=7, j=2: P[7]='A' == P[2]='A', 所以next[7] = j+1 = 3, 然后 i++, j++ -> i=8, j=3i=8, j=3: P[8]='B' == P[3]='B', 所以next[8] = j+1 = 4
最终得到的next数组为: [0, 0, 1, 2, 0, 1, 2, 3, 4]
4. KMP匹配过程
有了next数组，匹配过程就非常清晰了。
使用两个指针：
i：遍历主串T，永不回退。j：指向当前模式串P中正在匹配的位置。
匹配步骤：
- 初始化
i = 0,j = 0。 - 循环，直到
i到达主串末尾或j到达模式串末尾：
a. 如果T[i] == P[j]：
- 当前字符匹配，两个指针都后移 (i++,j++)。
b. 如果T[i] != P[j]：
- 如果j > 0：说明在模式串的j位置之前已经有字符匹配成功。根据next数组，将j回退到next[j-1]。注意：i指针不动！
- 如果j == 0：说明模式串的第一个字符就不匹配，那么只将主串指针i后移一位 (i++)。 - 判断匹配结果：
- 如果
j == len(P)，说明整个模式串匹配成功，返回起始位置i - j。 - 如果
i == len(T)，说明主串遍历完毕仍未匹配，返回-1表示失败。
- 如果
用之前的例子进行匹配：
T: "ABABDABACDABABCABAB"
P: "ABABCABAB"
next: [0,0,1,2,0,1,2,3,4]
i=0, j=0: T[0]='A' == P[0]='A' -> (i=1, j=1)i=1, j=1: T[1]='B' == P[1]='B' -> (i=2, j=2)i=2, j=2: T[2]='A' == P[2]='A' -> (i=3, j=3)i=3, j=3: T[3]='B' == P[3]='B' -> (i=4, j=4)i=4, j=4: T[4]='D' != P[4]='C' -> 不匹配，且 j=4>0, j回退到next[4-1]=next[3]=2- 现在
i=4, j=2: 比较 T[4]='D' 和 P[2]='A'，不匹配。j=2>0, j回退到next[2-1]=next[1]=0 - 现在
i=4, j=0: 比较 T[4]='D' 和 P[0]='A'，不匹配。且j=0，所以只i后移 -> (i=5, j=0) i=5, j=0: T[5]='A' == P[0]='A' -> (i=6, j=1)- ... (中间过程省略，直到再次发生不匹配或匹配成功)
- 最终，当
i和j移动到合适位置时，会完成整个模式串的匹配。
5. 总结
KMP算法通过预处理模式串得到next数组，记录了模式串自身的结构信息（最长公共前后缀）。在匹配失败时，利用next数组智能地移动模式串，避免了主串指针的回溯，将时间复杂度从暴力匹配的O(n*m)优化到了O(n+m)。理解并能够手动推导next数组是掌握KMP算法的关键。