public?static?class?Node{
? ? ? ?//當前節(jié)點值
? ? ? ?private?char?value;
? ? ? ?//當前節(jié)點的孩子節(jié)點
? ? ? ?private?Node[]?childNode;
? ? ? ?//標志當前節(jié)點是否是某單詞結尾
? ? ? ?private?boolean?isTail;
? ? ? ?//失敗指針
? ? ? ?private?Node?failNode;
? ? ? ?//匹配串長度，當isTail==true時，表示從root當當前位置是一個完整的匹配串，記錄這個匹配串的長度，便于之后快速找到匹配串
? ? ? ?private?Integer?tailLength;
? ? ? ?public?Node(char?value) {
? ? ? ? ? ?this.value?=?value;
? ? ? }
? }

Node?root;
? ?public?void?init() {
? ? ? ?root?=?new?Node('\0');
? ? ? ?root.childNode?=?new?Node[26];
? }

public?void?insertStr(char[]?chars) {
? ? ? ?//首先判斷首字符是否已經在字典樹中，然后判斷第二字符，依次往下進行判斷，找到第一個不存在的字符進行插入孩節(jié)點
? ? ? ?Node?p?=?root;
? ? ? ?//表明當前處理到了第幾個字符
? ? ? ?int?chIndex?=?0;
? ? ? ?while?(chIndex?<?chars.length) {
? ? ? ? ? ?while?(chIndex?<?chars.length?&&?null?!=?p) {
? ? ? ? ? ? ? ?Node[]?children?=?p.childNode;
? ? ? ? ? ? ? ?boolean?find?=?false;
? ? ? ? ? ? ? ?for?(Node?child?:?children) {
? ? ? ? ? ? ? ? ? ?if?(null?==?child) {continue;}
? ? ? ? ? ? ? ? ? ?if?(child.value?==?chars[chIndex]) {
? ? ? ? ? ? ? ? ? ? ? ?//當前字符已經存在，不需要再進行存儲
? ? ? ? ? ? ? ? ? ? ? ?//從當前節(jié)點出發(fā)，存儲下一個字符
? ? ? ? ? ? ? ? ? ? ? ?p?=?child;
? ? ? ? ? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? ? ? ? ? ? ? ?find?=?true;
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?if?(Boolean.TRUE.equals(find)) {
? ? ? ? ? ? ? ? ? ?//在孩子中找到了 不用再次存儲
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果把孩子節(jié)點都找遍了，還沒有找到這個字符，直接將這個字符加入當前節(jié)點的孩子節(jié)點
? ? ? ? ? ? ? ?Node?node?=?new?Node(chars[chIndex]);
? ? ? ? ? ? ? ?node.childNode?=?new?Node[26];
? ? ? ? ? ? ? ?children[chars[chIndex]?-?'a']?=?node;
? ? ? ? ? ? ? ?p?=?node;
? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? }
? ? ? }
? ? ? ?//字符串中字符全部進入tire樹中后，將最后一個字符所在節(jié)點標志為結尾節(jié)點
? ? ? ?p.isTail?=?true;
? ? ? ?p.tailLength?=?chars.length;
? }

public?void?madeFailNext() {
? ? ? ?//層序遍歷，為了保證求解這個節(jié)點失敗指針的時候，它的父節(jié)點的失敗指針以及失敗指針的失敗指針。。。。已經求得，可以完全根據(jù)這個找
? ? ? ?Deque<Node>?nodes?=?new?LinkedList<>();
? ? ? ?nodes.add(root);
? ? ? ?while?(!nodes.isEmpty()) {
? ? ? ? ? ?Node?current?=?nodes.poll();
? ? ? ? ? ?Node[]?children?=?current.childNode;
? ? ? ? ? ?for?(Node?child?:?children) {
? ? ? ? ? ? ? ?if?(null?==?child) {
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?Node?failNode?=?current.failNode;
? ? ? ? ? ? ? ?while?(null?!=?failNode) {
? ? ? ? ? ? ? ? ? ?//找到當前節(jié)點的失敗指針，查看失敗指針子節(jié)點是否有==
? ? ? ? ? ? ? ? ? ?Node[]?failChildren?=?failNode.childNode;
? ? ? ? ? ? ? ? ? ?Node?node?=?failChildren[child.value?-?'a'];
? ? ? ? ? ? ? ? ? ?if?(null?==?node) {
? ? ? ? ? ? ? ? ? ? ? ?//找當前指針的下一個指針
? ? ? ? ? ? ? ? ? ? ? ?failNode?=?failNode.failNode;
? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?//已經找到匹配的
? ? ? ? ? ? ? ? ? ?//將失敗指針指向node
? ? ? ? ? ? ? ? ? ?child.failNode?=?node;
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果找完還沒有找到，指向root
? ? ? ? ? ? ? ?if?(null?==?failNode) {
? ? ? ? ? ? ? ? ? ?child.failNode?=?root;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?nodes.add(child);
? ? ? ? ? }
? ? ? }
? }

/**
? ??* 匹配出str中所有出現(xiàn)的關鍵詞
? ??* @param str
? ??* @return
? ??*/
? ?public?List<String>?match(String?str) {
? ? ? ?//遍歷當前子串串，從根節(jié)點出發(fā)，如果匹配就一直往下進行匹配，同時需要看匹配的節(jié)點是否為結尾節(jié)點，如果是，匹配上一個
? ? ? ?//如果不匹配則通過失敗指針轉移到下一個節(jié)點
? ? ? ?this.dfs(root,?0,?str);
? ? ? ?return?machStr;
? }

? ?//abcdeasdabcebcd
? ?List<String>?machStr?=?new?ArrayList<>();
? ?private?void?dfs(Node?node,?int?chIndex,?String?chars) {
? ? ? ?if?(chIndex?>=?chars.length()) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?//從將當前字符與當前node的孩子節(jié)點進行匹配，如果當前字符與node的孩子節(jié)點.value匹配，判斷當前字符是否為尾節(jié)點，是，則記錄，匹配到了一個
? ? ? ?//繼續(xù)匹配（子節(jié)點，與下一個元素進行匹配）
? ? ? ?//如果不匹配，則轉到失敗指針
? ? ? ?Node[]?children?=?node.childNode;
? ? ? ?Node?child?=?children[chars.charAt(chIndex)?-?'a'];
? ? ? ?if?(null?==?child) {
? ? ? ? ? ?//不匹配，轉到失敗指針
? ? ? ? ? ?//如果當前node==root，從root匹配，root的失敗指針是null
? ? ? ? ? ?if?(node?==?root) {
? ? ? ? ? ? ? ?dfs(root,?++?chIndex,?chars);
? ? ? ? ? }?else?{
? ? ? ? ? ? ? ?dfs(node.failNode,?chIndex,?chars);
? ? ? ? ? }
? ? ? }?else?{
? ? ? ? ? ?//匹配到了
? ? ? ? ? ?if?(child.isTail) {
? ? ? ? ? ? ? ?//并且是結尾節(jié)點，取從child.value到child.tailLength的字符
? ? ? ? ? ? ? ?machStr.add(chars.substring(chIndex?-?child.tailLength??+?1,?chIndex?+?1));
? ? ? ? ? }
? ? ? ? ? ?dfs(child,?++?chIndex,?chars);
? ? ? }

? }

public?static?void?main(String[]?args) {
? ? ? ?ACAutomaton?acAutomaton?=?new?ACAutomaton();
? ? ? ?//初始化一個僅有根節(jié)點的字典樹
? ? ? ?acAutomaton.init();
? ? ? ?//構建Tire樹
? ? ? ?acAutomaton.insertStr("out".toCharArray());
? ? ? ?acAutomaton.insertStr("about".toCharArray());
? ? ? ?acAutomaton.insertStr("act".toCharArray());
? ? ? ?//構建失敗指針
? ? ? ?acAutomaton.madeFailNext();
? ? ? ?System.out.println("ces");
? ? ? ?//匹配
? ? ? ?List<String>?result?=?acAutomaton.match("abcdeasactdaboutcebcd");
? }