KMP算法如何构造DFA？

Question

《算法4》书中关于KMP算法的完整试下如下：public class KMP{    private String pat ;    private int[][] dfa ;    public KMP(String pat)    {        this.pat = pat ;        int M = pat.length() ;        int R = 256 ;        dfa = new int[R][M] ;        dfa[pat.charAt(0)][0] = 1 ;        for(int X=0 , j=1 ; j<M ; 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] ;        }    }    public int search(String txt)    {        int i , j , N=txt.length() , M = pat.length() ;        for(i=0 , j=0 ; i<N && j<M ; i++)        {            j = dfa[txt.charAt(i)][j] ;        }        if(j == M)            return i - M ;  //找到匹配        else            return N ; //表示为匹配    }}我唯一不理解的地方时在构造dfa数组时x的计算方法， 为什么X = dfa[pat.charAt(j)][X]？

Answer 1

<<算法>>上讲KMP我感觉将复杂了，我根本没看懂。
其实根本不用二维数组，建议你看看CSDN上一个叫July的人写的博文，讲的很清楚。