KMP算法:字符串匹配的全面指南

2024-10-05T17:37:25

Knuth-Morris-Pratt (KMP) 算法是一种高效的字符串匹配算法,它用于在一个文本串中搜索模式串的所有出现。与暴力匹配算法不同,KMP通过预处理步骤来避免不必要的比较,从而提高效率。在这篇博客中,我们将详细探讨KMP的工作原理、ne数组的构建过程,以及回退在算法中的关键作用。


目录

  1. 字符串匹配介绍
  2. KMP算法概述
  3. ne数组(部分匹配表)
  4. 逐步示例
  5. get_next函数:构建ne数组
  6. KMP匹配过程
  7. 回退示例
  8. 总结

1. 字符串匹配介绍

字符串匹配是计算机科学中的一个常见问题,即需要在给定的文本串 s 中找到模式串 p 的所有出现。暴力匹配算法通过逐字符比较,但这种方法在面对长字符串时效率低下。KMP算法通过避免冗余比较来提高效率,而这一切都归功于 ne 数组(部分匹配表)的预处理。


2. KMP算法概述

KMP算法分为两个阶段:

  1. 预处理阶段:构建模式串 pne 数组(部分匹配表)。
  2. 匹配阶段:利用 ne 数组在文本 s 中搜索模式串 p,当出现不匹配时,通过 ne 数组回退,避免重复比较。

关键概念:

  • ne 数组:记录模式串中每个位置的最长相等前缀和后缀的长度。
  • 回退(Retreating):当发生不匹配时,利用 ne 数组让模式串回退到之前已经匹配的部分,而不是从头重新开始匹配。

3. ne数组(部分匹配表)

ne 数组是 KMP 算法的核心,它记录了模式串中每个位置最长相等前缀和后缀的长度。

假设模式串 p = "ABABC",我们通过以下步骤构建 ne 数组:

逐步计算:

  1. 对于 p[1] = A,没有前缀或后缀,所以 ne[1] = 0
  2. 对于 p[2] = B,与 p[1] = A 不匹配,因此 ne[2] = 0
  3. 对于 p[3] = A,与 p[1] = A 匹配,因此 ne[3] = 1
  4. 对于 p[4] = B,与 p[2] = B 匹配,因此 ne[4] = 2
  5. 对于 p[5] = C,与 p[3] = A 不匹配,所以回退到 ne[4],最终 ne[5] = 0

最终的 ne 数组为 [0, 0, 1, 2, 0]


4. 逐步示例

示例:

让我们通过一个具体的例子来演示如何计算 ne 数组,对于模式串 p = "ABABC"

  1. i = 2 开始,比较 p[2] = Bp[1] = A不匹配,所以 ne[2] = 0
  2. 移动到 i = 3,比较 p[3] = Ap[1] = A匹配,所以 ne[3] = 1
  3. 移动到 i = 4,比较 p[4] = Bp[2] = B匹配,所以 ne[4] = 2
  4. i = 5 时,比较 p[5] = Cp[3] = A不匹配。因此我们使用 ne[4] = 2 回退,比较 p[5] = Cp[2] = B仍不匹配,所以 ne[5] = 0

这显示了如何通过回退避免从头开始匹配。


5. get_next函数:构建ne数组

get_next 函数用于构建 ne 数组。以下是函数代码及其解释:

void get_next() {  
    for (int i = 2, j = 0; i <= n; i++) {  // 从模式串的第2个字符开始  
        while (j && p[i] != p[j + 1]) j = ne[j];  // 当字符不匹配时,回退j  
        if (p[i] == p[j + 1]) j++;  // 如果匹配成功,j前进  
        ne[i] = j;  // 存储当前i位置的最长相等前后缀长度  
    }  
}
  • 解释

    • i 从模式串的第二个字符开始遍历。
    • p[i] != p[j + 1] 时,使用 ne[j] 回退 j
    • 当匹配成功时,j 增加,并更新 ne[i] 的值。
    • 该过程会一直持续到构建完整的 ne 数组。

6. KMP匹配过程

一旦我们构建了 ne 数组,KMP的匹配过程就可以高效地进行。具体步骤如下:

  1. 我们将模式串 p 与文本 s 进行比较。
  2. 如果字符匹配,两个指针(i 用于文本,j 用于模式串)同时前进。
  3. 如果出现不匹配,使用 ne 数组回退 j,而不需要重新设置 i
void kmp() {  
    for (int i = 1, j = 0; i <= m; i++) {  // 遍历主串  
        while (j && s[i] != p[j + 1]) j = ne[j];  // 当不匹配时,回退 j  
        if (s[i] == p[j + 1]) j++;  // 如果匹配,继续前进  
        if (j == n) {  // 如果模式串全部匹配完成  
            printf("%d ", i - n);  // 输出匹配起始位置  
            j = ne[j];  // 回退 j,寻找下一个可能的匹配  
        }  
    }  
}

关键点:

  • 当发生不匹配时,我们通过 ne 数组回退 j,避免从头开始匹配。
  • 与暴力匹配相比,这种方法显著提升了效率。

7. 回退示例

让我们使用文本 s = "ABABDABACDABABC" 和模式串 p = "ABABC" 来展示回退的实际操作:

  1. 开始时,s[1] = Ap[1] = A 匹配。
  2. 继续匹配 s[2] = Bp[2] = B,匹配成功。
  3. 直到 s[5] = Dp[5] = C 不匹配。
  4. 通过 ne[4] = 2,我们回退到 p[3] = A,然后与 s[5] = D 比较,仍然不匹配。
  5. 最终回退到 ne[2] = 0,重新从 p[1] 开始。

这一过程展示了如何利用回退机制避免不必要的比较。


8. 总结

KMP算法是一种高效的字符串匹配算法,通过预处理 ne 数组,在匹配过程中避免从头重新比较。ne 数组帮助记录最长相等前后缀的长度,回退的使用大大提升了匹配效率。


通过对 ne 数组的理解和使用,KMP算法能够极大提高字符串匹配的效率。希望本篇博客能够帮助你掌握KMP算法的核心思想并能够应用到实际项目中。

当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »