【算法】KMP算法详解

Algorithm

KMP（Knuth-Morris-Pratt）算法是一种用于字符串搜索的算法，它可以在一个文本字符串中搜索一个模式（即子字符串），其时间复杂度是O(n + m)，其中n是文本字符串的长度，m是模式的长度。KMP算法的关键优势是它能在不回溯文本串的指针的情况下，通过预处理模式串，实现快速的模式匹配。

KMP算法的核心思想：

KMP算法的核心是一个叫做“部分匹配表”（Partial Match Table）或者“最长公共前后缀”（Longest Prefix which is also Suffix，简称LPS）数组的预处理。这个表用于在发生不匹配时，决定文本字符串中的哪个位置应该是下一个比较的开始点，从而避免了从头开始比较。

如何构建LPS数组：

  1. 初始化： 创建一个LPS数组来保存每个前缀的最长公共前后缀长度。初始化一个变量 len 为 0，这个变量表示当前计算的最长的公共前后缀的长度，数组的第一个元素（LPS[0]）总是0。
  2. 处理： 从模式串的第二个字符开始处理到最后一个字符。
    • 如果当前字符和len指向的字符相同，就更新LPS数组，len加1。
    • 如果不同，减小len值，直到len为0或者找到一对相同的字符。
    • 将当前len的值赋给LPS数组。

如何使用LPS数组进行搜索：

  1. 初始化指针： 使用两个指针i和j分别跟踪文本和模式的位置。
  2. 匹配过程：
    • 当text[i]和pattern[j]匹配时，如果j是模式的最后一位，表示找到一个匹配，记录位置，j回退到LPS[j-1]。
    • 如果text[i]和pattern[j]不匹配，如果j不是0，将j回退到LPS[j-1]，否则i递增。
  3. 继续检查： 移动i，直到文本结束。

构建LPS数组的步骤详解：

假设我们有模式串 pattern = "ABABCABAA"，我们要构建一个LPS数组来表示每个前缀的最长公共前后缀长度。下面是构建LPS数组的具体步骤：

  1. 初始化：

    • len = 0（表示当前最长的公共前后缀长度）
    • LPS[0] = 0（第一个元素的最长公共前后缀长度为0，因为只有一个字符）

  2. 遍历模式串：

    • 从索引1开始，比较当前字符与len位置的字符。
    • 如果匹配，len增加1，并将len赋值给LPS[i]。
    • 如果不匹配，减少len直到0或找到匹配。如果找到匹配，如前所述操作；如果len减到0仍未匹配，LPS[i]设为0。

对于pattern = "ABABCABAA"，构建的LPS数组如下：

i Pattern[i] len LPS
0 A 0 0
1 B 0 0
2 A 1 1
3 B 0 0
4 C 0 0
5 A 1 1
6 B 2 2
7 A 3 3
8 A 1 1

使用LPS数组进行搜索的步骤详解：

假设我们有文本 text = "ABABABCABAAABABCABAA"，我们要在这个文本中搜索pattern = "ABABCABAA"。

  1. 初始化指针：

    • i = 0（文本的位置）
    • j = 0（模式的位置）

  2. 搜索过程：

    • 遍历文本，当text[i]和pattern[j]匹配时，递增i和j。
    • 如果j达到模式长度，表明找到一个完整匹配，记录匹配的起始位置i-j，然后将j回退到LPS[j-1]。
    • 如果text[i]和pattern[j]不匹配：
      • 如果j不是0，回退j到LPS[j-1]。
      • 如果j是0，则仅递增i。

对于我们的例子，首次匹配发生在文本的第10个字符开始。