字符串匹配 - KMP

刷题刷到字符串匹配相关的题，但是忘记KMP算法了。

此篇博客记录KMP复习。

问题背景

假设有两个字符串，一个是“文本串”（text），一个是“模式串”（pattern）。我们想知道模式串在文本串中出现的位置。

朴素匹配算法的问题

传统的字符串匹配算法会逐字符比较，如果发现不匹配，就从文本串的下一个字符开始重新匹配。这种方法在最坏情况下的时间复杂度是O(n*m)，n是文本串的长度，m是模式串的长度，效率较低。

KMP算法的核心思想

KMP算法的关键在于：当匹配失败时，如何利用已经匹配的信息，尽可能减少不必要的字符比较。

它通过“部分匹配表”来实现这一点。

部分匹配表也叫做前缀表

部分匹配表

部分匹配表记录了模式串中每个位置之前的字符串中相同的前缀和后缀的最长长度。通过这个表，当匹配失败时，我们可以直接跳到下一个可能的匹配位置，而不是重新开始。

“前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

例子

假设模式串是 ABABCABAB

部分匹配表的计算过程如下：

• 对于第一个字符 A，没有前缀和后缀，部分匹配表值为0。
• 对于前两个字符 AB，没有前缀和后缀相同，部分匹配表值为0。
• 对于前三个字符 ABA，前缀 A 和后缀 A 相同，部分匹配表值为1。
• 以此类推，计算出部分匹配表为 [0, 0, 1, 2, 0, 1, 2, 3, 4]。

KMP匹配过程

1. 我们从文本串的开始位置和模式串的开始位置比较。
2. 如果匹配，继续比较下一个字符。
3. 如果不匹配，根据部分匹配表调整模式串的位置，而不是简单地移动一位。

比如说对于文本串ABABCACBAKDNEKSIJNMGF

模式串ABABCABAB

第一次进行匹配的时候：

1 2 3 4 5 6 7 8

ABABCACBAKDNEKSIJNMGF ABABCABAB ^ i=6,j=6，发现模式串中索引为6的字符不匹配，但是索引0-5的字符都是匹配的。（此时指针i和指针j的值应该为） 下一步就直接跳跃到，i=6,j=1 ABABCACBAKDNEKSIJNMGF ABABCABAB ^

部分匹配表中 索引为5的值为1，表明模式串中索引0-5的子字符串最长公共前后缀长度为1。

4. 重复上述过程，直到找到所有匹配位置。

Java实现

构建部分匹配表（LPS数组）

在构建LPS（Longest Prefix which is also Suffix）数组时，要找到模式串中每个位置之前的字符串的最长前缀后缀长度。如果当前字符和前一个最长前缀字符不匹配，我们需要调整前缀长度，以便继续匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static int[] computeLPSArray(String pattern) {
    int length = pattern.length();
    int[] lps = new int[length];
    int j = 0; // 最长前缀后缀长度
    int i = 1;

    lps[0] = 0; // lps[0] 总是 0

    while (i < length) {
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
            lps[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = lps[j - 1]; // 利用之前计算的部分匹配表，调整 j 的值 ⭐
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

详细解释

假设我们有一个模式串 pattern 和当前的 LPS 数组 lps。我们用两个指针 i 和 j 来遍历模式串：

• i 指向当前处理的字符。
• j 记录最长前缀后缀的长度。

当 pattern[i] 和 pattern[j] 匹配时，我们增加 j 的长度，并设置 lps[i] = j。

不匹配处理⭐

参考：前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)

当 pattern[i] 和 pattern[j] 不匹配时，我们需要调整 j 的值：

• 如果 j != 0 ，说明我们之前已经有一部分匹配了。此时，我们不需要从头开始匹配，而是可以利用已经计算好的部分匹配表来减少比较次数。我们将 j 设置为 lps[j - 1]，即前一个位置的部分匹配值。⭐

• 如果 j == 0，则没有匹配的前缀，将 lps[i] 设为0，继续处理下一个字符 i++。

KMP匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// KMP 匹配算法
public static void KMPSearch(String text, String pattern) {
    int M = pattern.length(); // 模式串长度
    int N = text.length(); // 文本串长度

    int[] lps = computeLPSArray(pattern); // 计算部分匹配表（LPS数组）

    int i = 0; // text 的索引
    int j = 0; // pattern 的索引

    while (i < N) {
        if (pattern.charAt(j) == text.charAt(i)) { // 当前字符匹配
            i++;
            j++;
        }

        if (j == M) { // 完全匹配
            System.out.println("Found pattern at index " + (i - j));
            j = lps[j - 1]; // 调整 j 值，继续寻找下一个匹配
        } else if (i < N && pattern.charAt(j) != text.charAt(i)) { // 当前字符不匹配
            if (j != 0) {
                j = lps[j - 1]; // 调整 j 值，利用部分匹配表跳过已经匹配的部分
            } else {
                i++;
            }
        }
    }
}

详细解释

• M 是模式串的长度。

• N 是文本串的长度。

• lps 是部分匹配表，通过 computeLPSArray(pattern) 函数计算得到。

• i 和 j 分别是文本串和模式串的索引，用于遍历两个字符串。

通过 while 循环遍历整个文本串，寻找模式串的匹配位置。

1

while(i<N)

字符匹配

如果当前字符匹配，则继续比较下一个字符

1
2
3
4

if (pattern.charAt(j) == text.charAt(i)) {
    i++;
    j++;
}

如果 j 达到模式串的长度 M，说明找到了一个完整的匹配。

1
2
3
4

if (j == M) {
    System.out.println("Found pattern at index " + (i - j));
    j = lps[j - 1];
}

然后，将 j 设置为 lps[j - 1]，即部分匹配表中前一个位置的值，以便继续寻找下一个匹配。

字符不匹配

如果当前字符不匹配，根据 j 的值来决定下一步操作。

1
2
3
4
5
6
7

else if (i < N && pattern.charAt(j) != text.charAt(i)) {
    if (j != 0) {
        j = lps[j - 1];
    } else {
        i++;
    }
}

如果 j != 0，利用部分匹配表 lps 调整 j 的值为 lps[j - 1]，以便跳过已经匹配的部分。

如果 j == 0，说明没有任何部分匹配，直接将 i 加1，继续比较文本串的下一个字符。

可以看作在移动模式串pattern，如果比较到中途发现某一个字符不匹配，可以根据已经匹配部分的最长前后缀长度移动模式串pattern 。

参考资料

• KMP算法可视化

• 前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)