KMP算法主要解决的的是字符串匹配问题。 给定一个文本串T和一个模式串P，要求在文本串中找到模式串出现的位置。

引入：普通暴力匹配算法

最简单的字符串匹配算法是暴力匹配算法。其基本思想是：从文本串T的第一个字符开始，依次与模式串P的字符进行比较。如果遇到不匹配的字符，则将模式串向右移动一位，继续比较，直到找到匹配的位置或者文本串被扫描完为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int BFSearch(string T, string P) {
    int tsz = T.size();
    int psz = P.size();
    int t = 0; // T的指针
    int p = 0; // P的指针
    while (t <= tsz - psz && p < psz) {
        if (T[p + t] == P[p]) {
            p++;
        } else {
            t++;
            p = 0;
        }
    }
    if (p == psz) return t;
    return -1;
}

这种算法的时间复杂度达到了O(m*n)，其中m是文本串的长度，n是模式串的长度。为什么会出现这样的时间复杂度呢？考虑下面的例子：

1
2
T = "AAAAAAAAAAAAAB"
P = "AAAAB"

当两个字符串出现大量重复字符的时候，BF算法会反复回溯模式串的指针，导致时间复杂度上升。
而KMP算法通过计算最大前后缀匹配长度，避免了这种回溯，从而提高了匹配效率。

KMP算法原理

如果我们不想直接把指针回溯到零，我们应该如何确定回溯的长度呢？
观察下面的例子：

1
2
3
4
5
     012345678
T = "ABCABCABD"
          ^
P = "ABCABD"
          ^

可以看到，当我们匹配到T[5]和P[5]时发生了不匹配。但是我们注意到，在P和T已经匹配过的部分中，P[0,2]和T[3,5]是相同的字符串"ABC"。而P[0,2]又是P[0,4]的前缀，T[3,5]与P[0,4]的后缀相同。这样，我们只需要将模式串P向右移动2位，继续比较。

1
2
3
4
5
     012345678
T = "ABCABCABD"
          ^
P = "ABCABD"
       ^

这样，我们可以看到两个指针后续的字符串是相同的，继续逐个比较字符即可匹配成功。
这说明我们可以利用已经匹配成功的部分来避免不必要的比较。具体来说，我们需要找到模式串P的前缀和后缀的最长匹配长度，这样当发生不匹配时，我们可以将模式串向右移动相应的位数，避免重新匹配前面已经匹配过的部分。
这个最长匹配长度可以通过一个辅助数组next来存储。next[j]表示模式串P的前缀P[0..j-1]中，既是前缀又是后缀的最长子串的长度。

算法实现

先不考虑计算next数组，直接实现KMP匹配算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int kmp(string T, string P) {
    vector<int> next = computeNext(P);  // 计算next数组
    int pt = 0; // T的指针
    int pp = 0; // P的指针
    while (pt < T.size() && pp < P.size()) {
        if (T[pt] == P[pp]) {
            pt++;
            pp++;
        } else if (pp > 0) {
            pp = next[pp];  // 利用next数组回溯P的指针
        } else {
            pt++;
        }
    }
    if (pp == P.size()) return pt - pp;  // 返回开始匹配的位置
    return -1;
}

接下来实现计算next数组的函数：

定义：next[k] 表示模式串P[0,k-1]的最长前后缀匹配长度。
compare表示P[0,k-2]的最长前后缀匹配长度。

  1. 如果P[k - 1] = P[compare]，那么显然，next[k] = compare + 1（为什么不是next[k] = next[k - 1] + 1呢？）
  2. 如果P[k - 1] != P[compare]，则需要将compare向前回溯。假设更短的前后缀长度为m + 1，这里1表示后缀的最后一个元素，即P[k - 1]，那么需要满足前后缀相同的条件：P[0, m - 1] = P[k - m - 1, k - 2]。这样我们就把‘前后缀相等’这个要求向前递推了一位。假若这个时候前一位的前后缀存在匹配的情况，那么我们想要从匹配好的后缀中进一步取出长度为m的后缀，这个取出的‘子后缀’必然和匹配好的前缀的相应‘子后缀’相同，即P[compare - m, compare - 1]=P[k - m - 1, k - 2]（这是因为匹配的前后缀相同，所以它们相应位置的子串也相同）；同时，这个‘子后缀’还必须和整个P[0, k - 1]的长度为m的前缀相等，也就是上面写的条件。这样，我们发现了一个巧妙之处：P[compare - m, compare] = P[0, m - 1]，这表明m正是P[0, compare]的前后缀最大匹配长度！而P[0, compare]的最长前后缀匹配长度为next[compare]，因此我们可以将compare更新为next[compare]，如果满足条件1，则返回，否则继续，直到找到匹配或者compare为0。因此，前面不能简单地写成next[k] = next[k - 1]，因为next[k - 1]表示的是P[0, k - 2]的最长前后缀匹配长度，而我们需要的是在不匹配时，模式串指针应该回溯到的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> computeNext(string P) {
    if (P.size() < 2) return {0};
    vector<int> next(P.size(), 0);
    int compare = 0;
    int cur = 2;
    while (cur < P.size()) {
        if (P[cur - 1] == P[compare]) {
            compare++;
            next[cur] = compare;
            cur++;
        } else if (compare > 0) {
            compare = next[compare];
        } else {
            next[cur] = 0;
            cur++;
        }
    }
    return next;
}

总结

  1. 前后缀最大匹配长度有两层含义：一是表示前后缀的最大匹配长度，二是表示在发生不匹配时，模式串指针应该回溯到的位置。
  2. next求取时，分两种情况讨论，匹配和不匹配。不匹配时需要回溯compare指针，直到找到匹配或者compare为0。
  3. KMP算法的时间复杂度为O(m + n)，其中m是文本串的长度，n是模式串的长度。相比于暴力匹配算法，KMP算法在处理大量重复字符时表现更优。

参考例题：Leetcode 28. find the index of the first occurrence in a string

2026年1月3日。