字典樹結點package ac_auto; import java.util.*;public class TrieNode {public TrieNode[] childNodes;public int freq;public char nodeChar;public TrieNode faliNode;public Set<Integer> hashSet = new HashSet<Integer>();public TrieNode(){childNodes = new TrieNode[26];freq = 0;}}

AC自動機??流程

1?構造字典樹

2構造fail指針

3查找匹配

package ac_auto; import ac_auto.TrieNode;import java.util.*;public class Trie {public TrieNode trieNode = new TrieNode();public Queue<TrieNode> queue = new LinkedList<TrieNode>();public void AddTrieNode(char[] word, int id){AddTrieNode(trieNode, word, id);}public void AddTrieNode(TrieNode root, char[] word, int id){//求字符地址，方便將該字符放入到26叉樹中的哪一叉中int k = word[0]-'a';//如果該叉樹為空，則初始化if (root.childNodes[k] == null){root.childNodes[k] = new TrieNode();//記錄下字符root.childNodes[k].nodeChar = word[0];}char[] tmp=new char[26];for(int i=1;i<=word.length;i++){if (i==word.length)return;tmp[i-1]=word[i];word[i-1]=tmp[i-1];}char[] nextWord=tmp;//說明是最后一個字符，統計該詞出現的次數if (nextWord.length == 0){root.childNodes[k].freq++;root.childNodes[k].hashSet.add(id);}AddTrieNode(root.childNodes[k], nextWord, id);}public void BuildFailNodeBFS(){BuildFailNodeBFS(trieNode);}public void BuildFailNodeBFS(TrieNode root){//根節點入隊queue.offer(root);while (queue.peek() != null){//出隊TrieNode temp = queue.poll();//失敗節點TrieNode failNode = null;//26叉樹for (int i = 0; i < 26; i++){//代碼技巧：用BFS方式，從當前節點找其孩子節點，此時孩子節點// 的父親正是當前節點，（避免了parent節點的存在）if (temp.childNodes[i] == null)continue;//如果當前是根節點，則根節點的失敗指針指向rootif (temp == root){temp.childNodes[i].faliNode = root;}else{//獲取出隊節點的失敗指針failNode = temp.faliNode;//沿著它父節點的失敗指針走，一直要找到一個節點，直到它的兒子也包含該節點。while (failNode != null){//如果不為空，則在父親失敗節點中往子節點中深入。if (failNode.childNodes[i] != null){temp.childNodes[i].faliNode = failNode.childNodes[i];break;}//如果無法深入子節點，則退回到父親失敗節點并向root節點往根部延伸，直到null//（一個回溯再深入的過程，非常有意思）failNode = failNode.faliNode;}//等于null的話，指向root節點if (failNode == null)temp.childNodes[i].faliNode = root;}queue.offer(temp.childNodes[i]);}}}public Set<Integer> SearchAC(char[] s){Set<Integer> hash = new HashSet<Integer>();SearchAC(trieNode, s, hash);return hash;}public void SearchAC(TrieNode root, char[] s, Set<Integer> hashSet){int freq = 0;TrieNode head = root;int i;for(i=0;i<s.length-1;i++);{//計算位置int index =s[i]-'a';//如果當前匹配的字符在trie樹中無子節點并且不是root，則要走失敗指針//回溯的去找它的當前節點的子節點while ((head.childNodes[index] == null) && (head != root))head = head.faliNode;//獲取該叉樹head = head.childNodes[index];//如果為空，直接給root,表示該字符已經走完畢了if (head == null)head = root;TrieNode temp = head;//在trie樹中匹配到了字符，標記當前節點為已訪問，并繼續尋找該節點的失敗節點。//直到root結束，相當于走了一個回旋。(注意：最后我們會出現一個freq=-1的失敗指針鏈)while (temp!= root && temp.freq != -1){freq+= temp.freq;//將找到的id追加到集合中for(Integer item:temp.hashSet)hashSet.add(item);temp.freq = -1;temp = temp.faliNode;}}}public static void main(String args[]){Trie trie = new Trie();trie.AddTrieNode("say".toCharArray(),1);trie.AddTrieNode("she".toCharArray(),2);trie.AddTrieNode("shr".toCharArray(),3);trie.AddTrieNode("her".toCharArray(),4);trie.AddTrieNode("he".toCharArray(),5);Set<Integer> hashSet = new HashSet<Integer>();trie.BuildFailNodeBFS();char[] s = "yasherhs".toCharArray();hashSet= trie.SearchAC(s);String tmps=String.valueOf(s);System.out.println("在主串{0}中存在模式串的編號為:{1}");System.out.println(tmps);// Iterator<Integer> setIntIt =hashSet.iterator();// while(setIntIt.hasNext()){ System.out.println(hashSet);// }}}

總結

以上是生活随笔為你收集整理的java AC自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

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