写在前面：

（阅读本文前需要了解KMP算法的基本思路。另外，本着大道至简的思想，本文的所有例子都会做从头到尾的讲解）

作者翻阅了大量网上现有的KMP算法博客，发现广为流传的竟然是一种不完整的KMP算法。即通过next数组来作为有限状态自动机，以此实现非匹配时的回退。这不失为一种好的方法。

但我们接下来要见识的是一种更好和更完整的方法————拥有完整DFA的KMP算法

先列出本文要介绍的方法与一般方法对比下的几大优点：

1. 在最坏情况下，对字符串的操作次数仅为一般做法的三分之二。
2. 在所有情况下，对字符串的操作数都小于等于一般做法。
3. 思路上相对于一般做法更加完整细致，学习了它一定能让你对kmp有一个全新的认识。

 （读者可以在通读全文之后回头来看这几句话到底对不对）

一、关于有限状态自动机（什么是DFA）

kmp算法模拟了有限状态自动机的运行，一般算法中的next数组和本文中的dfa数组都是作为有限状态自动机的运行指导。

有限状态自动机不同，程序运行起来自然会存在不同。

在本文介绍的KMP算法中，我们使用二维数组DFA来作为有限状态自动机指导：

1. 定义：DFA=new int[R][M],R为文本可能出现的字符种类（EXTENDED_ASCII的R为256位，一般情况下是够用了），M为模式字符串的长度。
2. 空间：DFA占用空间上比next数组大了R倍，但空间的牺牲必然要迎来性能上的提升！
3. 储存内容：和next数组一样的是，DFA也储存了每个位置匹配失败时模式串的重启位置，但它更加详细，DFA针对了匹配失败时可能出现的不同字符对应了其特定的重启位置，这样的好处在后面的性能分析中会降到。

　　　　　　　　　图1　和模式字符串ABABAC对应的确定有限状态机自动机 

图一展示了模式字符串pat：ABABAC对应的确定有限状态机自动机

dfa[A][j]表示：模式串成功匹配到第j个位置时文本这时对应字符为'A'的情况下模式串下一个将要匹配的位置。

拿图1来说，dfa[A][3]表示匹配到模式串ABABAC的第三位时（B），文本对应的是A，这时模式串将回到dfa[A][3]=1，也就是将模式串回到ABABAC的第一位（B），然后继续下一位(也是就ABABAC中的第二位,这里是A)与文本的下一位继续比较。

似乎蛮复杂的，但理解了它的构造方法之，你就可以灵活使用它。

1、dfa的构造方法：

我们需要借助j和X来构造dfa，j指向当前的匹配位置，X是匹配失败时的重启位置。一开始j和X都设为0。

对于每个j，我们要做的是：

1. 将daf[][X]复制到daf[][j]（对于匹配失败的情况）
2. 将daf[pat.charAt(j)][j]设为j+1（对于匹配成功的情况）
3. 更新X

用代码表示如下：

（推荐读者先大概看看代码，再结合下面给出的完整例子，然后做代码运行调试）

dfa[pat.charAt(0)][0]=1; for(int X=0,j=1;j<M;j++){//计算dfa[][j]     for(int c=0;c<R;c++){//不匹配情况         dfa[c][j]=dfa[c][X];     }     dfa[pat.charAt(j)][j]=j+1;     X=dfa[pat.charAt(j)][X]; }    

在上面代码的基础上来演示一个完整的构造过程：

① j和X都为0，dfa[pat.charAt(0)][0]=1

② 进入for循环X=0,j=1：将X的列复制到j的列，再设dfa[pat.charAt(j)][j]=j+1，更新X