当前位置:   article > 正文

【数据结构】KMP算法概述_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数组,如下所示:

模式串ABD
next数组-100

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

文本串ABCDABD
模式串ABD
next数组-100

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

文本串ABCDABD
模式串ABD
next数组-100

此时,模式串中的"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算法,在效率上有一定的提升,但实现起来也更为复杂。因此,在实际应用时需要根据具体情况选择适合的算法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/662118
推荐阅读
相关标签
  

闽ICP备14008679号