KMP 字符串匹配算法

KMP(Knuth-Morris-Pratt) 算法是一种常见的字符串匹配算法，在主字符串 S 中查找字符串 M 出现的起始位置，通过 M 的自身信息来减少无效的查询次数。

下面以 S: ABDCABDFABDCABDE，M: ABDCABDE 来演示匹配过程:

其中 i 表示扫描的 S 的字符位置，j 表示扫描的 M 的字符位置，n 表示匹配的字符串长度

普通匹配

普通匹配的过程为，从 S 的第一个字符开始的 len(M) 个字符串与 M 进行匹配，如果匹配成功则返回位置，如果不成功则从 S 的第二个字符开始的 len(M) 个字符串与 M 进行匹配，循环向后进行匹配判断，直到剩余的字符串长度小于 len(M)，返回匹配失败。

• 从 S 的第一个字符开始进行逐个扫描对比:

此时匹配的长度 n 为 7， i 指向的值 F 和 j 指向的值 E 不同

• 回退 i 从 S 的第二个字符开始进行逐个扫描对比:

...

• 从 S 的第五个字符开始进行逐个扫描对比:

采用这种方式最终也可以找到 M 匹配 S 中的位置，但是该方式的匹配过程中可能存在多次的回退，即 i 指向位置的字符与 M 的字符不匹配时，若已匹配长度 n 不为 0，则 i 需要回退 (n-1) 个位置，从已比较过的字符开始重新逐个比较。

KMP算法

在了解KMP算法之前，首先看两个貌似无关的概念:前缀和后缀。前缀是指除最后一个字符或多个字符的字符串组合，后缀是指除第一个字符或多个字符的字符串组合。示例:

对于字符串:ABCAB，其前缀为 (A,AB,ABC,ABCA)，后缀为 (B,AB,CAB,BCAB)。取前缀和后缀中重复字符串的最大长度作为部分匹配长度。这里最长的重复字符串为:AB，即部分匹配长度为 2。

不妨以 len() 表示取字符串长度的函数。由概念可知，对于字符串 T，若其前缀和后缀的最长重复字符串为 PM，则 PM 完全匹配 T 的开头 len(PM) 个字符串，且完全匹配 T 的结尾 len(PM) 个字符串。即 PM 可以在字符串 T 中"滑动"匹配，"滑动"的长度为 len(T)-len(PM)。例如 T:ABCAB, PM:AB，则 PM "滑动"的长度为 5-2=3，即 AB 滑动 3 个字符后仍然完全匹配。

KMP算法中查找 M 在 S 中位置，在匹配过程中，通过分析 M 与 S 的已匹配字符串信息来避免回退现象，过程如下:

• 从 S 的第一个字符开始进行逐个扫描对比:

此时匹配的长度 n 为 7， i 指向的值 F 和 j 指向的值 E 不同

此时已匹配的字符串为 T:ABDCABD，长度为 7，由之前的概念可知，该字符串的部分匹配长度为 3，即字符串 PM:ABD 的长度。且字符串 ABD 滑动 7-3=4 个字符后仍然完全匹配 T 的结尾，即字符串 M 向右滑动 4 个字符，仍然存在 T:ABD 为已匹配字符串。

• 保持 i 指向的位置不变，将 M 右移 4 个字符继续进行扫描对比：

此时已匹配的字符串为 T:ABD，长度为 3， 部分匹配长度为 0，则下一步可以向右滑动 3-0=3 个字符。

• 保持 i 指向的位置不变，将 M 右移 3 个字符继续进行扫描对比：

...

KMP 算法保证了 i 指向的 S 中位置不需要进行回退，可以减少无效的回退造成的性能浪费。在实际代码中不存在将 M 右移 len(T)-len(PM) 个字符的操作，可以直接更新 j 的值为 len(PM) 即可，指向待比较的字符位置。