网上有很多关于KMP算法的文章。用google搜“kmp算法”，第一页的文章我都看过，唯一能看懂并看完的就只有阮一峰的这篇。

KMP算法很难懂，难在它的具体代码实现十分简洁，简洁得一点都看不出其背后的思想。今天就着算法第四版说几个理解KMP的关键点：

  • 暴力字符串匹配的复杂度最差的情况可以达到 N*M ，而 KMP 算法最差是 N+M ，高效的原因之一在于文本指针永远不会回溯。每一次比较，文本指针都递增 1 ，只有模式字符串的指针在回溯
  • KMP 高效的原因之二是就算匹配失败，模式字符串的指针在回溯也不是一味回到最初的位置，它会根据部分已经成功匹配的字符串以及当前匹配失败的输入决定回溯到哪个位置，参考上文提到的文章，会对这有感性的认识
  • 上文提到的 部分已经成功匹配的字符串 ，具体举例说明： 
    ...A B A B A D A... <-------- 文本中间的某一段
   A B A B A C <-------- 模式字符串
             ↑

    箭头所指是匹配失败之处，当前输入是 D ，已经成功匹配的字符串是 A B A B A ，部分已经成功匹配的字符串是指 除去第一个字母 A 后的已经成功匹配的字符串： B A B A 。因为每一次比较，文本指针都递增 1 （本例中，文本指针将会指向 D 后面的 A ），再从模式字符串中选出一个字母与之比较。成功匹配的字符串中最左边的那个字母之后再也没有机会与模式字符串比较了。决定该从模式字符串中选出哪一个字母的是 部分已经成功匹配的字符串以及当前输入。

  • KMP 使用了有限状态自动机，要理解书中的图5.3.6以及图5.3.9，最好的办法是自己动手一步步实现dfa数组：

    1 首先说明数组行和列的意义，自动机最初处于 0 状态，结束于 6 状态，它将根据当前所在状态及输入决定下一个状态，数组中每个元素的值对应于自动机状态。输入只列出 A B C ，因为其它输入都会令自动机回退到状态 0 ，所以省去不写。

      0 1 2 3 4 5 <------ 这是有限状态自动机的各个状态
  A B A B A C <------ 这是模式字符串
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 
B
C
↑
这
是
输
入

    2 当自动机处于 0 状态，且输入 A 时，就会进入 1 状态；输入 B 或 C 时，还是处于 0 状态

      0 1 2 3 4 5
  A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1
B 0
C 0

    3 可以先把能让自动机从 0 到 6 状态的输入写出来。当自动机处于 1 状态，且输入 B 时，就会进入 2 状态，依次类推：

      0 1 2 3 4 5
  A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1   3   5
B 0 2   4
C 0         6

    4 那些空白的数组元素又该怎样处理呢？具体举一例来说，当自动机处于 1 状态，且输入 A 时，会进入哪个状态呢？首先自动机肯定不能进入下一个状态 2 ，只能是回退到状态 0 或者 状态 1 ；然后请回答一个问题：已知自动机当前状态是 1 ，当前输入是 A （当前输入是什么都无所谓），请问前一个输入是什么？ 答案是 A ，因为只有输入 A 才能使自动机由前一个状态 0 进入到当前状态 1 。这个 A 就是上文所说的已经成功匹配的字符串，那么部分已经成功匹配的字符串是已经成功匹配的字符串除去最左边的字母(A)，即：空字符串。 最后假设因为当前的输入与模式字符串失配，导致自动机直接回退到状态 0 ，自动机要先跟部分已经成功匹配的字符串逐个匹配，再与当前输入匹配，才能得出下一个状态。部分已经成功匹配的字符串是空字符串，当前输入是 A ，所以自动机由状态 0 进入到状态 1 。同理，当自动机处于 1 状态，且输入 C 时，会回退到 0 状态。我们填好了第二列，如下：

      0 1 2 3 4 5
  A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3   5
B 0 2   4
C 0 0       6

    5 接下来填写第三列，当自动机处于 2 状态，且输入 B 时，会进入哪个状态呢？首先自动机肯定不能进入下一个状态 3 ，只能是回退到状态 0 或者 状态 1 或者 状态 2；然后请回答一个问题：已知自动机当前状态是 2 ，请问前两个输入是什么？ 答案是 AB ，因为只有输入 AB 才能使自动机由初始状态 0 进入到当前状态 2 。 AB 就是上文所说的已经成功匹配的字符串，部分已经成功匹配的字符串是 B 。最后假设因为当前的输入与模式字符串失配，导致自动机直接回退到状态 0 ，部分已经成功匹配的字符串是 B ，当前输入是 B ，自动机处于状态 0 时先与部分已经成功匹配的字符串逐个匹配，再与当前输入匹配。显然在输入了两个 B 之后，自动机还是处于状态 0。同理，当自动机处于 2 状态，且输入 C 时，会回退到 0 状态。我们填好了第三列，如下：

      0 1 2 3 4 5
  A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3   5
B 0 2 0 4
C 0 0 0     6

    6 当自动机处于 3 状态，且输入 A 时，会进入哪个状态呢？长话短说，已知自动机当前状态是 3 ，已经成功匹配的字符串是 A B A ，部分已经成功匹配的字符串是 B A ，当前输入是 A ，假设自动机因失配直接回退到状态 0 ，自动机处于状态 0 时先与部分已经成功匹配的字符串逐个匹配，再与当前输入匹配（合起来就是 B A A），最后会停留在状态 1 。输入 C 时，同理。我们填好了第四列，如下：

      0 1 2 3 4 5
  A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3 1 5
B 0 2 0 4 0
C 0 0 0 0 0 6

    7 同理，我们填好了第五列，如下：

      0 1 2 3 4 5
  A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3 1 5 1
B 0 2 0 4 0 4
C 0 0 0 0 0 6
  • 接下来说说书中构造dfa代码中的X。书中说X是重启位置。我更倾向于认为 X 是自动机的状态。拿更新X时用到的代码X = dfa[pat.charAt(j)][X]来说，等号左边的 X 代表了自动机的下一个状态，pat.charAt(j)表示当前的输入，等号右边的 X 表示自动机当前的状态。举例来说，dfa第二列，X 等于 0，j 等于 1，c 从 0 到 R ， 
      dfa[0][1] = dfa[0][0]
  dfa[1][1] = dfa[1][0]
  dfa[2][1] = dfa[2][0]
  .
  .
  .
  dfa[R][1] = dfa[R][0]

    上面等式的意义就在于，它能根据当前状态 0 ，以及当前输入 0 ~ R ，得出自动机——除成功匹配的下一状态之外——的下一状态。你也可以认为它只是简单地把在当前状态匹配输入后的状态，直接赋值给下一状态匹配输入后的状态。 在给dfa第二列赋值后，X 的值更新为 X = dfa[pat.charAt(1)][0] = dfa['B'][0] = 0， 在给dfa第三列赋值后，X 的值更新为 X = dfa[pat.charAt(2)][0] = dfa['A'][0] = 1， 在给dfa第四列赋值后，X 的值更新为 X = dfa[pat.charAt(3)][1] = dfa['B'][1] = 2， 在给dfa第五列赋值后，X 的值更新为 X = dfa[pat.charAt(4)][2] = dfa['A'][2] = 3， 在给dfa第六列赋值后，X 的值更新为 X = dfa[pat.charAt(5)][3] = dfa['C'][3] = 0

参考