這里實現了基于有限自動機（Finite Automaton,FA）的模式匹配算法，算法的重點在于利用字符串的前后綴構造模式P的自動機，具體結合導論中的說明來理解，可參考http://www.geeksforgeeks.org/searching-for-patterns-set-5-finite-automata/理解，參考代碼如下：

package cn.ansj;public class AtuomatonMatcher {final public static int NO_OF_CHARS=256;//假設字母表有256個字符//對于狀態k和給定的字符x，返回下一個狀態。M為pat的長度public static int getNextState(char[] pat, int M, int k, int x){// 因為:pat[0...k-1]x 和 pat 的前面都是是一樣的，如果x == pat[k]可直接返回。if (k < M && x == pat[k])return k+1;int ns, i; // ns 是下一個狀態// ns 最終是最長的那個 prefix (同時也是pat[0..k-1]x)的后綴//從可能得最長的前綴位置開始，找到后break,即為所求for (ns = k; ns > 0; ns--) {if(pat[ns-1] == x){for(i = 0; i < ns-1; i++) {if (pat[i] != pat[k-ns+1+i])break;}if (i == ns-1)return ns;}}return 0;}/* 構建FA */public static void computeTF(char[] pat, int M, int[][] TF){int state, x;for (state = 0; state <= M; ++state)for (x = 0; x < NO_OF_CHARS; ++x)TF[state][x] = AtuomatonMatcher.getNextState(pat, M, state, x);}/* 查找模式串 */public static void matcher(char[] pat, char[] txt){int M = pat.length;int N = txt.length;//TF數組存儲FA有限狀態機int[][] TF=new int[M+1][NO_OF_CHARS];AtuomatonMatcher.computeTF(pat, M, TF);//計算模式pat的有限自動機// Process txt over FA.int i, state=0;for (i = 0; i < N; i++) {state = TF[state][txt[i]];if (state == M){int index=i-M+1;System.out.println("pattern found at index:"+index);} }}public static void main(String[] args){String strTxt="AABAACAADAABAAABAA";String strPat="AABA";char[] txt = strTxt.toCharArray();char[] pat = strPat.toCharArray();AtuomatonMatcher.matcher(pat, txt);} }
執行結果：

pattern found at index:0 pattern found at index:9 pattern found at index:13

總結

以上是生活随笔為你收集整理的Java实现算法导论中有限自动机字符串匹配算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。