搜尋

首頁  >  問答  >  主體

java - KMP算法如何构造DFA?

《算法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]

阿神阿神2889 天前373

全部回覆(1)我來回復

  • 迷茫

    迷茫2017-04-17 17:34:06

    <<演算法>>上講KMP我覺得將複雜了,我根本沒看懂。
    其實根本不用二維數組,建議你看看CSDN上一個叫July的人寫的博文,講的很清楚。

    回覆
    0
  • 取消回覆