java - 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的人寫的博文，講的很清楚。