cari

Rumah  >  Soal Jawab  >  teks badan

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 hari yang lalu371

membalas semua(1)saya akan balas

  • 迷茫

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

    <<Algoritma>>Saya rasa ia akan menjadi rumit apabila bercakap tentang KMP, dan saya tidak faham langsung.
    Malah, tatasusunan dua dimensi tidak digunakan sama sekali, saya cadangkan anda membaca catatan blog yang ditulis oleh seseorang bernama Julai di CSDN, yang menerangkannya dengan sangat jelas.

    balas
    0
  • Batalbalas