【数据结构】KMP算法概述_kmp算法时间复杂度

KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的算法。它的核心思想是利用已知信息来避免无用的比较操作，从而提高算法效率。KMP算法的时间复杂度为O(n + m)，其中n为模式串的长度，m为文本串的长度。

本文将介绍基础的KMP算法和它的变种。

标准的KMP算法

KMP算法的基本思想是，当模式串中的某个字符与文本串中的某个字符匹配失败时，KMP算法利用已经匹配成功的信息，跳过一部分不必要的比较操作，直接从模式串的已匹配部分的下一个字符开始继续匹配。

下面我们来看一下KMP算法的实现代码。假设我们有一个文本串text和一个模式串pattern，要求判断text中是否包含pattern。

代码如下：

public static boolean kmp(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    if (n < m) { // 特判，文本串长度小于模式串长度，直接返回false
        return false;
    }
    // 计算next数组
    int[] next = getNext(pattern);
    // 从前往后匹配
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j]; // 跳过一部分不必要的比较操作
        }
    }
    return j == m; // 如果j等于m，说明匹配成功，返回true，否则返回false
}

// 计算next数组
private static int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    int i = 0, j = -1;
    next[0] = -1;
    while (i < m - 1) {
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}
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
29
30
31
32
33
34
35
36
37
38

在上述代码中，我们先特判一下文本串长度小于模式串长度的情况，直接返回false。然后我们计算出模式串的next数组，接着从前往后遍历文本串和模式串，如果当前字符匹配失败，就从next数组中找到跳跃的位置，直接从模式串的已匹配部分的下一个字符开始继续匹配。最后如果模式串的所有字符都能匹配成功，则返回true，否则返回false。

下面给出一个示例来说明KMP算法的具体运作过程。假设我们要在文本串"ABCDABD"中查找模式串"ABD"。首先我们根据模式串计算出next数组，如下所示：

接着我们开始遍历文本串和模式串，如下所示：

显然，文本串中"A"和模式串中"A"匹配成功，继续比较下一个字符；文本串中"B"和模式串中"B"匹配成功，继续比较下一个字符；文本串中"C"和模式串中"D"匹配失败，此时我们根据next数组计算出跳跃的位置是0，所以直接从文本串的下一个字符"C"和模式串的第一个字符"A"继续开始匹配。

此时，模式串中的"A"和文本串中的"A"匹配成功，继续比较下一个字符；模式串中的"B"和文本串中的"B"匹配成功，继续比较下一个字符；模式串中的"D"和文本串中的"D"匹配成功，说明模式串完全匹配文本串，KMP算法返回true，匹配成功。

通过这个例子，我们可以看到KMP算法利用了已知信息跳过了一部分不必要的比较操作，从而提高了算法效率。

值得注意的是，在计算next数组时，为了方便处理j == 0的情况，我们将next[0]初始化为-1。在匹配过程中，当j == -1时，说明模式串的第一个字符就与文本串中的当前字符匹配失败，因此直接将i和j同时+1即可。这一点需要特别注意。

综上所述，KMP算法是一种高效的字符串匹配算法，其核心思想是利用已知信息跳过不必要的比较操作，同时不会漏掉任何一个匹配。

变种KMP算法（Z算法）

除了上述基础的KMP算法，还有一种优化过的KMP算法，称为改进的KMP算法（也称Z算法）。

Z算法的核心思想是将原始的next数组优化为Z数组，从而避免了计算next数组时的回溯操作。

Z数组的计算过程较为复杂，这里不再赘述，有兴趣的读者可以自行了解。需要注意的是，Z数组的长度一定等于模式串的长度，因此需要将文本串和模式串拼接在一起，用特殊符号分隔开来，以避免越界。

下面是改进的KMP算法的代码实现：

public static boolean kmp(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    char[] s = new char[n + m + 1];
    int[] z = new int[n + m + 1];
    text.getChars(0, n, s, 0);
    pattern.getChars(0, m, s, n + 1);
    s[n] = '#';
    int l = 0, r = 0;
    for (int i = 1; i <= n + m; i++) {
        if (i <= r) {
            z[i] = Math.min(z[i - l], r - i + 1);
        }
        while (i + z[i] <= n + m && s[i + z[i]] == s[z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
        if (z[i] == m) {
            return true;
        }
    }
    return false;
}
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

在这个算法中，我们首先将文本串和模式串拼接在一起，并用特殊符号进行分隔，然后对拼接后的字符串计算Z数组（也称为Z函数）。Z数组z[i]表示以第i个字符为开头的子串与整个字符串的最长公共前缀长度（不包括第i个字符本身）。具体实现上，我们维护一个区间[l,r]，表示已知的最长公共前缀的右端点r，左端点l即为当前i对应的区间左端点。如果i在[l,r]区间内，则可以利用已知信息避免无用的比较操作，直接计算z[i]的初始值；否则，需要从s[i]开始暴力匹配。如果z[i]达到了模式串的长度m，则说明匹配成功，返回true。

需要注意的是，在计算z[i]时，我们在检查s[i+z[i]]和s[z[i]]是否匹配时，应该首先判断i+z[i]是否在[l,r]区间内，这样才能利用已知信息避免无用的比较操作。

总的来说，改进的KMP算法相较于基础的KMP算法，在效率上有一定的提升，但实现起来也更为复杂。因此，在实际应用时需要根据具体情况选择适合的算法。