public?static?class?Node{
? ? ? ?//當(dāng)前節(jié)點(diǎn)值
? ? ? ?private?char?value;
? ? ? ?//當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
? ? ? ?private?Node[]?childNode;
? ? ? ?//標(biāo)志當(dāng)前節(jié)點(diǎn)是否是某單詞結(jié)尾
? ? ? ?private?boolean?isTail;
? ? ? ?//失敗指針
? ? ? ?private?Node?failNode;
? ? ? ?//匹配串長(zhǎng)度，當(dāng)isTail==true時(shí)，表示從root當(dāng)當(dāng)前位置是一個(gè)完整的匹配串，記錄這個(gè)匹配串的長(zhǎng)度，便于之后快速找到匹配串
? ? ? ?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) {
? ? ? ?//首先判斷首字符是否已經(jīng)在字典樹中，然后判斷第二字符，依次往下進(jìn)行判斷，找到第一個(gè)不存在的字符進(jìn)行插入孩節(jié)點(diǎn)
? ? ? ?Node?p?=?root;
? ? ? ?//表明當(dāng)前處理到了第幾個(gè)字符
? ? ? ?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]) {
? ? ? ? ? ? ? ? ? ? ? ?//當(dāng)前字符已經(jīng)存在，不需要再進(jìn)行存儲(chǔ)
? ? ? ? ? ? ? ? ? ? ? ?//從當(dāng)前節(jié)點(diǎn)出發(fā)，存儲(chǔ)下一個(gè)字符
? ? ? ? ? ? ? ? ? ? ? ?p?=?child;
? ? ? ? ? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? ? ? ? ? ? ? ?find?=?true;
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?if?(Boolean.TRUE.equals(find)) {
? ? ? ? ? ? ? ? ? ?//在孩子中找到了 不用再次存儲(chǔ)
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果把孩子節(jié)點(diǎn)都找遍了，還沒(méi)有找到這個(gè)字符，直接將這個(gè)字符加入當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
? ? ? ? ? ? ? ?Node?node?=?new?Node(chars[chIndex]);
? ? ? ? ? ? ? ?node.childNode?=?new?Node[26];
? ? ? ? ? ? ? ?children[chars[chIndex]?-?'a']?=?node;
? ? ? ? ? ? ? ?p?=?node;
? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? }
? ? ? }
? ? ? ?//字符串中字符全部進(jìn)入tire樹中后，將最后一個(gè)字符所在節(jié)點(diǎn)標(biāo)志為結(jié)尾節(jié)點(diǎn)
? ? ? ?p.isTail?=?true;
? ? ? ?p.tailLength?=?chars.length;
? }

public?void?madeFailNext() {
? ? ? ?//層序遍歷，為了保證求解這個(gè)節(jié)點(diǎn)失敗指針的時(shí)候，它的父節(jié)點(diǎn)的失敗指針以及失敗指針的失敗指針。。。。已經(jīng)求得，可以完全根據(jù)這個(gè)找
? ? ? ?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) {
? ? ? ? ? ? ? ? ? ?//找到當(dāng)前節(jié)點(diǎn)的失敗指針，查看失敗指針子節(jié)點(diǎn)是否有==
? ? ? ? ? ? ? ? ? ?Node[]?failChildren?=?failNode.childNode;
? ? ? ? ? ? ? ? ? ?Node?node?=?failChildren[child.value?-?'a'];
? ? ? ? ? ? ? ? ? ?if?(null?==?node) {
? ? ? ? ? ? ? ? ? ? ? ?//找當(dāng)前指針的下一個(gè)指針
? ? ? ? ? ? ? ? ? ? ? ?failNode?=?failNode.failNode;
? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?//已經(jīng)找到匹配的
? ? ? ? ? ? ? ? ? ?//將失敗指針指向node
? ? ? ? ? ? ? ? ? ?child.failNode?=?node;
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果找完還沒(méi)有找到，指向root
? ? ? ? ? ? ? ?if?(null?==?failNode) {
? ? ? ? ? ? ? ? ? ?child.failNode?=?root;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?nodes.add(child);
? ? ? ? ? }
? ? ? }
? }

/**
? ??* 匹配出str中所有出現(xiàn)的關(guān)鍵詞
? ??* @param str
? ??* @return
? ??*/
? ?public?List<String>?match(String?str) {
? ? ? ?//遍歷當(dāng)前子串串，從根節(jié)點(diǎn)出發(fā)，如果匹配就一直往下進(jìn)行匹配，同時(shí)需要看匹配的節(jié)點(diǎn)是否為結(jié)尾節(jié)點(diǎn)，如果是，匹配上一個(gè)
? ? ? ?//如果不匹配則通過(guò)失敗指針轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)
? ? ? ?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;
? ? ? }
? ? ? ?//從將當(dāng)前字符與當(dāng)前node的孩子節(jié)點(diǎn)進(jìn)行匹配，如果當(dāng)前字符與node的孩子節(jié)點(diǎn).value匹配，判斷當(dāng)前字符是否為尾節(jié)點(diǎn)，是，則記錄，匹配到了一個(gè)
? ? ? ?//繼續(xù)匹配（子節(jié)點(diǎn)，與下一個(gè)元素進(jìn)行匹配）
? ? ? ?//如果不匹配，則轉(zhuǎn)到失敗指針
? ? ? ?Node[]?children?=?node.childNode;
? ? ? ?Node?child?=?children[chars.charAt(chIndex)?-?'a'];
? ? ? ?if?(null?==?child) {
? ? ? ? ? ?//不匹配，轉(zhuǎn)到失敗指針
? ? ? ? ? ?//如果當(dāng)前node==root，從root匹配，root的失敗指針是null
? ? ? ? ? ?if?(node?==?root) {
? ? ? ? ? ? ? ?dfs(root,?++?chIndex,?chars);
? ? ? ? ? }?else?{
? ? ? ? ? ? ? ?dfs(node.failNode,?chIndex,?chars);
? ? ? ? ? }
? ? ? }?else?{
? ? ? ? ? ?//匹配到了
? ? ? ? ? ?if?(child.isTail) {
? ? ? ? ? ? ? ?//并且是結(jié)尾節(jié)點(diǎn)，取從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();
? ? ? ?//初始化一個(gè)僅有根節(jié)點(diǎn)的字典樹
? ? ? ?acAutomaton.init();
? ? ? ?//構(gòu)建Tire樹
? ? ? ?acAutomaton.insertStr("out".toCharArray());
? ? ? ?acAutomaton.insertStr("about".toCharArray());
? ? ? ?acAutomaton.insertStr("act".toCharArray());
? ? ? ?//構(gòu)建失敗指針
? ? ? ?acAutomaton.madeFailNext();
? ? ? ?System.out.println("ces");
? ? ? ?//匹配
? ? ? ?List<String>?result?=?acAutomaton.match("abcdeasactdaboutcebcd");
? }