《算法4》書中關(guān)于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 ; //表示為匹配 }}我唯一不理解的地方時在構(gòu)造dfa數(shù)組時x的計算方法, 為什么X = dfa[pat.charAt(j)][X]?
1 回答

翻翻過去那場雪
TA貢獻2065條經(jīng)驗 獲得超14個贊
<<算法>>上講KMP我感覺將復雜了,我根本沒看懂。
其實根本不用二維數(shù)組,建議你看看CSDN上一個叫July的人寫的博文,講的很清楚。
添加回答
舉報
0/150
提交
取消