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的人写的博文，讲的很清楚。