LeetCode-0324~28

leetCode1032

思路：想的是维护一个后缀数组，然后用Set去判断一下，结果超时了，去看题解，好家伙AC自动机，没办法，开始学。

正确题解：

class ACNode{public ACNode[] children;public boolean exist;public ACNode fail;public ACNode(){this.children = new ACNode[26];this.exist = false;this.fail = null;}public ACNode FindFail(int ch){ACNode tmp = this.fail;while(tmp!=null&&tmp.children[ch]==null)tmp = tmp.fail;return tmp;}
}class Trie{public ACNode root;public Trie(){this.root = new ACNode();}public void insert(String p){ACNode tmp = this.root;for(int i=0;i<p.length();i++){char ch = p.charAt(i);int it = ch - 'a';ACNode child = tmp.children[it];if(child==null){child = new ACNode();tmp.children[it] = child;}tmp = tmp.children[it];}tmp.exist = true;}
}class StreamChecker {private Trie root;private ACNode current;public StreamChecker(String[] words) {this.root = new Trie();this.current = this.root.root;for(int i=0;i<words.length;i++){this.root.insert(words[i]);}Queue<ACNode> queue = new LinkedList<>();for(int i=0;i<26;i++){ACNode child = this.current.children[i];if(child!=null){child.fail = this.current;queue.offer(child);}}//  BFSwhile(!queue.isEmpty()){ACNode tmp = queue.poll();for(int i=0;i<26;i++){ACNode child = tmp.children[i];if(child!=null){ACNode fail = tmp.FindFail(i);if(fail!=null){child.fail = fail.children[i];child.exist = fail.children[i].exist||child.exist;}else{child.fail = this.current;}queue.offer(child);}}}}public boolean query(char letter) {ACNode tmp = this.current;int it = letter - 'a';while(tmp.fail!=null&&tmp.children[it]==null)tmp = tmp.fail;if(tmp.children[it]!=null){this.current = tmp.children[it];}else{this.current = this.root.root;}if(this.current.exist){return true;}else {return false;}}
}

之前代码也记录一下吧，虽然过不了

class StreamChecker {private Set<String>wordset;private String postfix[];public StreamChecker(String[] words) {this.wordset = new HashSet<String>();this.postfix = new String[]{};for(int i=0;i<words.length;i++){this.wordset.add(words[i]);}}public boolean query(char letter) {int len = this.postfix.length;String newPostfix[] = new String[len+1];boolean flag = false;if(len==0)newPostfix[0]=""+letter;else {for(int i=0;i<len;i++)newPostfix[i]=this.postfix[i]+letter;newPostfix[len]=""+letter;}this.postfix=newPostfix;for(int i=0;i<this.postfix.length;i++){if(this.wordset.contains(this.postfix[i])){flag = true;break;}}return flag;}
}/*** Your StreamChecker object will be instantiated and called as such:* StreamChecker obj = new StreamChecker(words);* boolean param_1 = obj.query(letter);*/

AC自动机

与KMP同时期算法，用于多模式匹配

同样给你一个T串，你要搜索多个单词（p串），如果是KMP的话，有几个单词就搜几遍，AC自动机进过预处理之后，只要扫描一遍T串就可以把p串里面的单词都找出来。

字典树：

1. root节点最大有26个孩子，字母a-z
2. 图中有两个圈的点代表单词真正的结尾
3. 查找失败：
   1. 查找字母时发现是空指针
   2. 找到了单词，但是发现没有这个标记，不是一个单词

fail指针

1. 如果i的fail指针是j，则word[j]是word[i]的最长后缀。
   1. 例如9指向4 则说明he是she的最长后缀。
   2. 再例如，10指向3 ，hers的最长后缀是ers但是字典树里面并没有，所以只能指向s。
   3. 如果fail指针指向root，则说明该单词没有后缀在该字典里面
2. 利用fail指针查询，一个一个字母进行查询：
   1. 字母a：root查询失败，回到root
   2. 字母h：查询到，一直到his整个单词都可以查到。
   3. 第二个字母h：匹配失败，会跳转到失败指针所指：3好点。多模匹配就是利用单词共同的部分去查找，如果是KMP的话，他会从头再去找hshe，但是利用单词之间共同的后缀部分，可以跳过部分匹配工作。这样一直到节点九，查找到了单词she。并且再进行匹配为空，顺着fail指针到4号。
   4. 字母e找到了he单词，然后顺着找又找到了hers。
3. 为什么顺着fail指针移动可以多模匹配：利用了单词的后缀可能是其他单词的前缀的关系
4. 不仅要检测是否存在，还需要检测存在的位置

预处理过程（fail指针+exist单词信息）

1. 根据p串里面的单词构建字典树
2. 例如1->2->3构建出完整的单词，在该节点存储一个数组，存储以次字母结尾的单词长度。
3. 实现fail指针：使用bfs层序遍历
   1. 对于单个字母，前后缀为空，直接指向root；字典树第一次的fail指针都会指向root
   2. 对于深度大于1的节点，他的fail指针需要用到父节点的失败指针，他会观察父fail指针有没有和他字母一样的孩子。如果为空，也会指向root，否则，会指向对应节点。
4. 如果一个单词的结尾节点的fail指针指向了另一个单词的结尾节点，则该单词的结尾数组里面会追加一个单词长度信息。

查找T串

1. 查a：从root出发，root没有此儿子，空串，还是在root不动。
2. 查h：从root出发，root有h，但是里面exist信息为空，虽然是节点单不是p串单词，继续从h出发匹配
3. 查i：从h出发，h有儿子i，同样exist为空，继续
4. 查s：从i出发，i有s儿子，且有exist信息，此时T串迭代器it为3，p串长度为3，回退3个就是1-3是p串单词his。继续匹配，从10号节点s出发
5. 查h：从s出发，s没有h这个儿子，走fali指针到4号匹配。4号有h儿子，到达5号节点，exist为空，继续查。
6. 查e：从h（5号）出发，h有e这个儿子，且exist有货，同时找到了she和he两个单词。继续查
7. 查r：e没有r，走fail指针到3号，3号e确实有r儿子，exist为空，继续查
8. 查s：r有s，且exist有货，找到hers单词

代码实现

字典树

这里要求会写BFS和字典树，字典树的实现写了一下：

// 仅匹配小写字母，如果想广泛匹配，可以修改children数组
class TrieNode{private TrieNode[] children;private boolean isEndOfWord;public TrieNode(){this.children = new  TrieNode[26];this.isEndOfWord = false;}public TrieNode[] getChildren(){return this.children;}public boolean isEndOfWord(){return this.isEndOfWord;}public void setEndOfWord(boolean endOfWord){this.isEndOfWord=endOfWord;}
}public class Trie {private TrieNode root;public Trie(){root = new TrieNode();}public void insert(String word){TrieNode current = this.root;for(int i=0;i<word.length();i++){char ch = word.charAt(i);TrieNode child = current.getChildren()[ch-'a'];if(child==null){child = new TrieNode();current.getChildren()[ch-'a'] = child;}current = child;}current.setEndOfWord(true);}public boolean search(String word){TrieNode current = this.root;for(int i=0;i<word.length();i++){char ch = word.charAt(i);TrieNode child = current.getChildren()[ch-'a'];if(child==null){return false;}current = child;}return current.isEndOfWord();}
}

AC自动机

class ACNode {public ACNode[] children;List<Integer> exist;public ACNode fail;public ACNode(){this.children = new ACNode[26];this.exist = new ArrayList<>();this.fail = null;}/*** 如果i.fail指向j,则j是i的最长后缀，如果此时j是一个单次的话，就要将j的exist也转存的i的exist中*/public void AddExist(List<Integer> exist){if(exist==null||exist.size()==0)return;for(int i=0;i<exist.size();i++){this.exist.add(exist.get(i));}}/*** 迭代寻找失败指针，只有当找到时或者*/public ACNode FindFail(int c){ACNode tmp = this.fail;while (tmp!=null&&tmp.children[c]==null){tmp = tmp.fail;}return tmp;}
}class TrieTree{public ACNode root;public TrieTree(){this.root = new ACNode();}public void insert(String p){ACNode current = this.root;for(int i=0;i<p.length();i++){char ch = p.charAt(i);int it = ch-'a';ACNode child = current.children[it];if(child==null){child = new ACNode();current.children[it] = child;}current = current.children[it];}current.exist.add(p.length());}
}public class AC_automaton {private TrieTree root;public AC_automaton(){this.root = new TrieTree();}/*** 构建字典树，并且生成fail指针*/public void build(String p[]){for(int i=0;i<p.length;i++){this.root.insert(p[i]);}//  开始补全fail指针Queue<ACNode> queue = new LinkedList<>();//  处理第一层ACNode root = this.root.root;for(int i=0;i<26;i++){if(root.children[i]!=null){root.children[i].fail=root;queue.offer(root.children[i]);}}//  BFSwhile (!queue.isEmpty()){ACNode current = queue.poll();for(int i=0;i<26;i++){ACNode child = current.children[i];if(child!=null){queue.offer(child);//  调用迭代查找ACNode fail = current.FindFail(i);if(fail==null){child.fail=root;}else {child.fail=fail.children[i];//  将最长后缀的exist数组继承过来child.AddExist(fail.children[i].exist);}}}}}/*** 匹配T串*/public void query(String T){if(T==null||T.length()==0)return;ACNode current = this.root.root;for(int i=0;i<T.length();i++){char ch = T.charAt(i);int it = ch-'a';while (current.fail!=null&&current.children[it]==null){current=current.fail;}if(current.children[it]!=null){current = current.children[it];}else{continue;}if(current.exist.size()>0){for(int j=0;j<current.exist.size();j++){int l = current.exist.get(j);if(i-l+1<0){System.out.print("Error: i-l<0!");continue;}String str = T.substring(i-l+1,i+1);System.out.println("找到字符串："+str);}}}}
}

测试：

public class MyTest {@Testpublic void TestTrieInsert(){Trie root = new Trie();root.insert("trie");System.out.print(root);}@Testpublic void TestAC_automaton(){AC_automaton acAutomaton = new AC_automaton();acAutomaton.build(new String[]{"he","hers","his","she"});acAutomaton.query("ahishers");}}

结果：

找到字符串：his
找到字符串：she
找到字符串：he
找到字符串：hers