字符串匹配——KMP与有限状态自动机

前言

本文记录了一下自己对KMP和有限状态自动机算法的理解，方便复习

KMP与有限状态自动机算法其实我认为可以看做是同一个算法，他们具有相同的本质，即利用最长公共前后缀

但他们对这个思想的实现不一样，本文先介绍KMP，进而在理解KMP的基础上再介绍有限状态自动机算法。

目录
  • 前言
  • 第一部分 KMP
    • 算法介绍
      • 暴力算法
      • 最长公共前后缀
      • 算法过程
    • 理解字符串匹配
    • 如何寻找最长公共前后缀
    • C++代码实现
    • 复杂度分析
      • 时间复杂度
  • 第二部分 有限状态自动机算法
    • 什么是有限状态自动机
    • 算法介绍
    • 如何构造有限状态自动机
      • Q
      • Σ
      • F
      • δ
    • C++代码实现
    • 复杂度分析
      • 时间复杂度
  • 第三部分 总结

第一部分 KMP

算法介绍

暴力算法

首先看我们在字符串匹配时最原始的暴力算法，在text中找到pattern

int find(string pattern, string text) {
  for (int i = 0->text.length() - 1) {
    for (int j = 0->pattern.length() - 1) {
      if (text[i + j] != pattern[j]) {
        break;
      }
      if (j == pattern.length() - 1) {
        return i;
      }
    }
  }
}

算法的时间复杂度是O(mn)，m是pattern的长度，n是text的长度（下文沿用m和n这两个记号）

简单解释就是对于text中每一个字符，我们都检查以他为开头的子串是否匹配pattern

在KMP中，我们借用公共前后缀的概念，可以避免许多重复的检查

最长公共前后缀

什么是公共前后缀？

假设在一个字符串 s = "abaaba" 中，子串 "aba" 既是 "abaaba" 的前缀也是他的后缀，"aba" 就是 s 的公共前后缀，同理 "a" 也是 s 的公共前后缀，我们将一个字符串中长度最长的公共前后缀称为该字符串的最长公共前后缀，以下我们用 “前缀” 来代指作为前缀时的最长公共前后缀，在上面的例子中，即为 "abaaba"的前三个字符，“后缀”同理，代指作为后缀时的最长公共前后缀，即 "abaaba" 的后三个字符

（本文使用的前缀、后缀均不包含字符串自身也不包含空串，即 proper prefix/postfix）

我们将最长公共前后缀的概念应用于字符串匹配，下面是匹配算法的流程

算法过程

记 i 为text的下标，j 为pattern的下标，均初始化为0

假设我们有一个next数组，next[x]记载的是子串pattern[0-x]的最长公共前后缀长度，怎么求next[x]我们会在后面讲解

算法步骤：

  1. 若text[i] == pattern[j]，则i++, j++，代表的是 text 中的字符和 pattern 中的字符成功匹配，两个下标均往后走一位，匹配下一个字符
  2. 若text[i] != pattern[j]，则j = next[j-1]，代表的是，不匹配时，使 j 退到 pattern[0-j-1] 的“前缀”的后一位

重复以上步骤直到 j = m-1（成功匹配）或 i = n-1 （匹配失败）

让我们来举个例子

假设 text 为"ababaca"， pattern 为"abababa"，我们要在text中找到pattern

通过算法步骤1，我们很容易就跑到了 i = 5，此时我们已完成了前5个字符"ababa"的匹配

现在我们去匹配第6个字符 text[ i=5 ] 与 pattern[ j=5 ]，但我们发现 'c' 与 'b' 不匹配。此时我们做的不是将 i 回退到text[1]，j 回退到0，完全重新匹配一次。在KMP中，我们的 i 永远只会往后走，我们需要回退pattern的下标 j，使 j = next[j-1] = 3。在pattern[0-j-1] : "ababa" 的最长公共前后缀是"aba"，我们将j退到pattern[0-j-1]的"前缀”的后一位，下标就是next[j-1]，text不用退，i不变，继续用text[i]与pattern[j]匹配

因为text[ i=5 ]与pattern[ j=3]还是不匹配，pattern[0-j-1]: "aba"的最长公共前后缀是"a"，使 j = next[j-1]，即把j退到"a"的后一位，j = 1

j=1, i=5时还是不匹配，但pattern[0-j-1]不存在最长公共前后缀，我们使 j=0

若 j=0时仍不匹配，则使 i++，重复算法步骤，直到 j = m- 1 或 i = n - 1

这样我们就完成了KMP的字符串匹配，代码如下

  for (int i = 0 -> n-1) {
    while (j > 0 && text[i] != pattern[j]) {
      j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
      j++;
    }
    if (j == m) {
      return i - m + 1;
    }
  }

但此时我们还不知道，为什么要在字符不匹配时将 j 回退到pattern[0-j-1]前缀的后一位，和如何找到最长公共前后缀

理解字符串匹配

我们先讲为什么要在字符不匹配时，将 j 回退到 pattern[0-j-1] 前缀的后一位

我们使用上面的例子，text为"ababaca"， pattern为"abababa"

当匹配到第6个字符时，i=5，j=5，text[i] != pattern[j]

此时满足如下几个条件

  1. pattern[0-4] = text[0-4]
  2. A是pattern[0-4]的“前缀”，A = B

由 1 可以推导出

  1. B = D

进而可以推导出 A = D

A = D 代表着，pattern[0-2]与text[2-4]已经自动成功匹配，我们接下来就应该用pattern[3]与text[5]比较，即将j回退到3，i不变。可以看出通过这种方式，我们省去了重复匹配pattern[0-2]的过程，这就是我们为什么要找“最长公共前后缀”，也是KMP的威力所在。

让我们继续往下看上面的例子，可以理解得更透彻一点，现在比较pattern[3]与text[5]，并不匹配

此时满足以下几个条件

  1. pattern[0-2] = pattern[2-4]
  2. pattern[2-4] = text[2-4]
  3. A是pattern[0-2]的“前缀”，A = B
  4. E = F

和我们之前的推导一样，我们根据1和3可以推导出

  1. pattern[0-2] = text[2-4]

再根据1，得到

  1. B = E

加上条件3得到

  1. A = E

根据5和8，得到结论

A = F

A = F代表着，pattern[0]与text[4]成功匹配，我们接下来就应该用pattern[1]与text[5]比较，而不需要重复比较pattern[0]和 text[4]

我们应该已经明白了，利用起最长公共前后缀，可以大大地减少比较次数

如何寻找最长公共前后缀

接下来我们会讲解如何找到最长公共前后缀

我们需要找到的是pattern[0/-1]，pattern[0/-2] , ... ，pattern[0-m-1]的最长公共前后缀长度，与 text 无关

我们用数组next来记录最长公共前后缀长度， next[ x ]记载的是子串pattern[0-x]的最长公共前后缀长度

用 i 和 j 来作为 pattern的下标，我们要找的始终是next[ j ]，i 记录的是pattern[0-j] “前缀” 的最后一位（也有可能不是，请继续往下看），先初始化 i = 0，j = 1，next[0]可以直接写入0，因为一个字符不存在最长公共前后缀（我们前面提到了前后缀不包括自己）

算法的步骤如下：

若 pattern[ i ] == pattern[ j ]，next[ j ] = i+1，i++，j++

当匹配成功时，i 记录的是 “前缀” 最后一位，i+1就是“前缀”的长度，写入next[j]

可以看这个下面例子

pattern[0] == pattern[1]，i记录的是pattern[0-1]的前缀 "a" 的最后一位，使next[j] = i + 1，到下一个状态

因为pattern[0] = pattern[1]，我们知道了A = B，我们在 A = B 的基础上想进一步知道

A+pattern[1] == B+pattern[2] 是否为真，如果为真的话我们可以得到一个长度为2的最长公共前后缀，事实上确实是为真的，我们就使next[j] = i+1，i++，j++。可以看出我们在利用已知的最长公共前后缀来帮助推导新的最长公共前后缀

我们省略中间简单的步骤，直接到 i = 3 , j = 5 的情况

此时已知A = B，但pattern[3] != pattern[4]，我们此时就需要讲若 pattern[i] != pattern[j] 怎么办

若 pattern[i] != pattern[j]，使 i = next[i-1]，再比较pattern[i]与pattern[j]，若仍不匹配，继续使 i = next[i-1]，直到 i = 0 为止，若 i = 0 时匹配成功，按照我们上面讲的pattern[i] = pattern[j] 的情况处理，若不匹配，i不动，j++。重复以上步骤，直到next数组填满

让我们沿用上面的例子来讲解一下这个算法

虽然 A = B 这个结论无法使用，但我们找到A的最长公共前后缀，回退到前缀后一位

A = B 蕴含着隐含条件，C = D，我们在算法理解第一部分已经有过类似的推导，但在这里还是重复一遍

已知条件

  1. A = B

根据1可知

  1. A[1-2] = B[1-2]， 即 pattern[1-2] = pattern[2-3]

A中最长公共前后缀是"aa"，可知

  1. pattern[0-1] = pattern[1-2]

根据2和3，得到

  1. pattern[0-1] = pattern[2-3]，即C = D

虽然 A = B 利用不成功，但我们还可以利用起 C = D 来找最长公共前后缀，所以将i退到 C 后一位，但因为仍不匹配，需要继续回退，退到C的最长公共前后缀的后一位。重复以上的步骤，直到 i = 0 ，这下我们知道了没有任何已知的公共前后缀可以给我们利用，只能从头开始匹配，若 i = 0时头尾也不匹配，说明pattern[0-j]不存在公共前后缀，next[ j ]记为0，使 j++，找此时pattern[0-j]的最长公共前后缀

上面的例子在回退时并没有利用起我们已经算出来的最长公共前后缀，下面这个例子是可以利用的情况

这种情况下，A+pattern[i] 与 B+pattern[j]不匹配，但我们可以利用A的最长公共前后缀

我们可以推导出 C = D，而且此时 C +pattern[i] = D + pattern[j] 为真，可以得到 pattern[0-j]的最长公共前后缀是 C+1，利用起了已经算出的最长公共前后缀

到这里我们就知道如何计算next数组（最长公共前后缀）了，而且我们可以发现，字符串匹配部分和构造next的算法是非常相似的，这是因为不仅字符串匹配是在利用next数组，连next数组的构造也在使用自己

到这里，KMP的详解就结束了

这个算法可以总结为两步

  1. 找next数组
  2. 利用next数组去匹配字符串

下面是代码实现

C++代码实现

#include 
using std::string;
void find_next(string pattern, int* next);

int KMP(string pattern, string text) {
  int m = pattern.length();
  int n = text.length();
  int* next = new int[m];
  for (int i = 0; i < m; i++) {
    next[i] = 0;
  }
  find_next(pattern, next);
  int j = 0;
  for (int i = 0; i < n; i++) {
    while (j > 0 && text[i] != pattern[j]) {
      j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
      j++;
    }
    if (j == m) {
      return i - m + 1;
    }
  }
  return -1;
}

void find_next(string pattern, int* next) {
  int m = pattern.length();
  int head = 0;
  next[0] = 0;
  for (int tail = 1; tail < m; tail++) {
    while (head > 0 && pattern[head] != pattern[tail]) {
      head = next[head - 1];
    }
    if (pattern[head] == pattern[tail]) {
      head++;
    }
    next[tail] += head;
  }
}

复杂度分析

时间复杂度

待写

第二部分 有限状态自动机算法

什么是有限状态自动机

有限状态自动机的英文叫做finite-state automaton，也叫finite-state machine，这里引用了我老师程京德教授上课使用的课件中，对finite-state automaton的介绍，解释的非常简洁明了

再简单解释以下

Q就是这个有限状态自动机中存在的状态的集合

Σ是能输入这个有限状态自动机的字符的集合

δ是从 Q与Σ的笛卡尔积 到 Q 上的函数，叫做状态转移方程，意思是在状态A接受一个输入字符x，会转移到δ(A,x)状态

q0是开始的状态，F是一系列接受状态的集合，当转移到F其中的状态，有限状态自动机就会结束工作

如果将A输入M，最终能根据 δ 转移到accepted states，我们将A称为是M的语言，也叫"M recognizes A"

而且M如果recognize A，要满足 δ(qi，wi+1) = qi+1，这个条件我们待会会用到

算法介绍

这个算法，要在text中找到pattern，我们要根据pattern来构建一个有限状态自动机 M，并将 text 输入 这个有限状态自动机，判断 M 是否 recognize text

所以这个算法的重点就落在如何根据 pattern 构造一个有限状态自动机

如何构造有限状态自动机

一个有限状态自动机包含 5 个元素，只要确定他们便构造完成，下文是对各个元素的逐一确定

下文将我们构造的有限状态自动机简称为M

Q

当 pattern 长度为m，Q 的 cardinality 应该为 m+1，即有 m+1 个元素，分别为q0，q1，... ，qm，q0就是start state

Σ

根据 pattern 而定，本文暂定为ASCII中0-255所代表的字符

F

accepted states只包含一个元素，就是qm

δ

这个是构造有限状态自动机的重点部分，下文会阐述如何确定δ

假设 pattern 为 "aabaaabb"，这个例子中 alphabet只有"a"和"b"，便于讲解

下方这个表是δ的初始状态，我们要根据pattern填满从state 0到state (m-1)的内容

表中每个格子要写入的是，在当前state下，接受这个input，会转移到哪个state，比如 δ(1,b) 代表的是在q1时接受input "b"，将会转移到的state

填表的第一条规则是：当处于qx，input是pattern[x]，qx转移到qx+1，这与上文提到的有限状态自动机 M accept w 第二个条件一致

根据这条规则，这个表有一部分我们可以很容易地就根据pattern每个位置的字符来写入

把δ用于字符串匹配，当我们的输入到达了state qx，代表已经完成了前x个字符的匹配，当到达q8，代表匹配成功

假设我们此时的 text 刚好和 pattern 完全相同，我们理应能够直接顺序地从q0走到q8

将这个与pattern完全相同的 text 输入M。当状态为q0时，遇到 text 第一个字符 "a" 就应该进入 q1 。当状态为 q1 时，遇到 pattern 第二个字符 "a" 就应该进入 q2 。省略中间一大段过程，直接到当状态为q7时，遇到"b"就应该进入q8，也就是the accepted state

这样看来，如果只根据第一条规则填表，也是可以完成字符串匹配的。但如果 text 和 pattern 不完全相同呢？我们先把剩余的格子都填入 0

这代表的是，每次匹配失败，就回到q0，从头开始匹配，这和我们的暴力算法是一致的。但如果有好的规则来规定δ，不用在每次匹配失败时都要回到q0，可以省去许多重复的匹配。

于是，科学家设计了这个算法，和KMP一样，利用了最长公共前后缀，来省略重复的匹配

具体机制如下

先规定，在q0，除了字符匹配成功，其他输入都应该使状态不变，即 δ(0, x) = 0（x != pattern[0]）

现在我们有一个变量 j 和一个变量next，j 初始化为0，next的值跟着 j 的变化而变化

next 的值应该等于将pattern[1-j]输入M后，最后到达的状态

根据这个规则，我们先算出 j=0 时的next，因为pattern[1-j]不存在，输入M后，仍在q0，所以next=0

我们确定δ剩余格子的规则如下，

当处于qj，若pattern[j] != input，δ( j，input ) = δ( next(j)，input )

根据这条规则，得到δ(1，b) = δ(next=0，b) = 0

当 j=1，pattern[1-1]为a，输入M后，到达了q1，所以此时next=1，δ(2，a) = δ(1，a) = 2

当 j=2，pattern[1-2]为ab，输入M后，还是在q0，此时next=0，δ(3，b) = δ(0，b) = 0

对于next，有一个更快的计算方法，每次更新 j，next = δ(next, pattern[j])，代表的是在原先next所在的状态添加上新的字符

通过这些规则，我们就可以填满δ和得到各个阶段的next了，结果如下

借用我老师唐博教授的图，用下面这个示意图可以更容易理解δ

但δ中规定的状态回退的原理是什么呢？我们现在来看看

把pattern[1-j]输入M中，最后走到的状态用next记录，实际上，next就是pattern[0-j]最长公共前后缀的长度，因为我们已经根据pattern[0-j]构造完成了M从q0到qj的部分 ，把pattern[1-j]输入M，可以找到pattern[1-j]的末尾，有多长的子串和pattern[0-j]开头的子串完全相同，也就是去找pattern[0-j]的最长公共前后缀。

举个例子

当 j=6，我们已经构造好了M从 q0 到 q6 的部分，pattern[1-6]最后3个字符是"aab"，当把pattern[1-6]输入M，最终会到达q3，因为 "aab" 与pattern[0-6]前3个字符相同，3也就代表着pattern[0-6]的最长公共前后缀的长度

实际上，δ也是在用自己构造自己，这点KMP中的next数组一致

当我们知道了这个原理，也就明白了为什么，当处于qj，若pattern[j] != text[j]，δ( j，input ) = δ( next，input )

这本质上是在用输入的字符和pattern[0-j]的“前缀”的后一位匹配，省略了一部分“自动完成”的比较，这里的字符串匹配原理和KMP中的几乎完全一样，若还不完全理解的可以回到第一部分KMP的“理解字符串匹配”部分复习一下，但不同的是

到这里，用于字符串匹配的有限状态自动机算法就讲完了。

C++代码实现

#include 
#define total_chars 256
#define trans_func(i, j) (trans_func[(i) * (m) + (j)])

using std::string;

void transition(int* trans_func, string pattern, int m);

int FSA(string pattern, string text) {
  int m = pattern.length();
  int n = text.length();
  int* trans_func = new int[total_chars * m];
  transition(trans_func, pattern, m);
  int q = 0;
  for (int i = 0; i < n; i++) {
    q = trans_func(text[i], q);
    if (q == m) {
      return i - m + 1;
    }
  }
  return -1;
}

void transition(int* trans_func, string pattern) {
  int m = pattern.length();
  for (int i = 0; i < total_chars; i++) {
    if (i == pattern[0]) {
      trans_func(i, 0) = 1;
    } else {
      trans_func(i, 0) = 0;
    }
  }
  int X = 0;
  for (int j = 1; j < m; j++) {
    for (int i = 0; i < total_chars; i++) {
      if (pattern[j] == i) {
        trans_func(i, j) = j + 1;
      } else {
        trans_func(i, j) = trans_func(i, X);
      }
    }
    X = trans_func(pattern[j], X);
  }
}

复杂度分析

时间复杂度

待写

第三部分 总结

当我们把两种算法都理解透彻了，发现他们两个只是一种思想的两种实现方式

KMP中的next数组和有限状态自动机算法中的next其实是一样的，都是记录了最长公共前后缀的长度

字符串匹配部分都是使用了最长公共前后缀的概念，省去了重复的匹配部分，十分精妙

数据结构与算法分析

相关

标签