网站建设网上售票系统,优设网址导航属于网络导航吗,网站看不到预览图,免费企业网站源代码leetCode1032
思路#xff1a;想的是维护一个后缀数组#xff0c;然后用Set去判断一下#xff0c;结果超时了#xff0c;去看题解#xff0c;好家伙AC自动机#xff0c;没办法#xff0c;开始学。
正确题解#xff1a;
class ACNode{public ACNode[] children;publi…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!nulltmp.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 i0;ip.length();i){char ch p.charAt(i);int it ch - a;ACNode child tmp.children[it];if(childnull){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 i0;iwords.length;i){this.root.insert(words[i]);}QueueACNode queue new LinkedList();for(int i0;i26;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 i0;i26;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!nulltmp.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 SetStringwordset;private String postfix[];public StreamChecker(String[] words) {this.wordset new HashSetString();this.postfix new String[]{};for(int i0;iwords.length;i){this.wordset.add(words[i]);}}public boolean query(char letter) {int len this.postfix.length;String newPostfix[] new String[len1];boolean flag false;if(len0)newPostfix[0]letter;else {for(int i0;ilen;i)newPostfix[i]this.postfix[i]letter;newPostfix[len]letter;}this.postfixnewPostfix;for(int i0;ithis.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串里面的单词都找出来。
字典树 root节点最大有26个孩子字母a-z图中有两个圈的点代表单词真正的结尾查找失败 查找字母时发现是空指针找到了单词但是发现没有这个标记不是一个单词
fail指针 如果i的fail指针是j则word[j]是word[i]的最长后缀。 例如9指向4 则说明he是she的最长后缀。再例如10指向3 hers的最长后缀是ers但是字典树里面并没有所以只能指向s。如果fail指针指向root则说明该单词没有后缀在该字典里面 利用fail指针查询一个一个字母进行查询 字母aroot查询失败回到root字母h查询到一直到his整个单词都可以查到。第二个字母h匹配失败会跳转到失败指针所指3好点。多模匹配就是利用单词共同的部分去查找如果是KMP的话他会从头再去找hshe但是利用单词之间共同的后缀部分可以跳过部分匹配工作。这样一直到节点九查找到了单词she。并且再进行匹配为空顺着fail指针到4号。字母e找到了he单词然后顺着找又找到了hers。 为什么顺着fail指针移动可以多模匹配利用了单词的后缀可能是其他单词的前缀的关系不仅要检测是否存在还需要检测存在的位置
预处理过程fail指针exist单词信息
根据p串里面的单词构建字典树例如1-2-3构建出完整的单词在该节点存储一个数组存储以次字母结尾的单词长度。实现fail指针使用bfs层序遍历 对于单个字母前后缀为空直接指向root字典树第一次的fail指针都会指向root对于深度大于1的节点他的fail指针需要用到父节点的失败指针他会观察父fail指针有没有和他字母一样的孩子。如果为空也会指向root否则会指向对应节点。 如果一个单词的结尾节点的fail指针指向了另一个单词的结尾节点则该单词的结尾数组里面会追加一个单词长度信息。
查找T串 查a从root出发root没有此儿子空串还是在root不动。查h从root出发root有h但是里面exist信息为空虽然是节点单不是p串单词继续从h出发匹配查i从h出发h有儿子i同样exist为空继续查s从i出发i有s儿子且有exist信息此时T串迭代器it为3p串长度为3回退3个就是1-3是p串单词his。继续匹配从10号节点s出发查h从s出发s没有h这个儿子走fali指针到4号匹配。4号有h儿子到达5号节点exist为空继续查。查e从h5号出发h有e这个儿子且exist有货同时找到了she和he两个单词。继续查查re没有r走fail指针到3号3号e确实有r儿子exist为空继续查查sr有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.isEndOfWordendOfWord;}
}public class Trie {private TrieNode root;public Trie(){root new TrieNode();}public void insert(String word){TrieNode current this.root;for(int i0;iword.length();i){char ch word.charAt(i);TrieNode child current.getChildren()[ch-a];if(childnull){child new TrieNode();current.getChildren()[ch-a] child;}current child;}current.setEndOfWord(true);}public boolean search(String word){TrieNode current this.root;for(int i0;iword.length();i){char ch word.charAt(i);TrieNode child current.getChildren()[ch-a];if(childnull){return false;}current child;}return current.isEndOfWord();}
}AC自动机
class ACNode {public ACNode[] children;ListInteger 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(ListInteger exist){if(existnull||exist.size()0)return;for(int i0;iexist.size();i){this.exist.add(exist.get(i));}}/*** 迭代寻找失败指针只有当找到时或者*/public ACNode FindFail(int c){ACNode tmp this.fail;while (tmp!nulltmp.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 i0;ip.length();i){char ch p.charAt(i);int it ch-a;ACNode child current.children[it];if(childnull){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 i0;ip.length;i){this.root.insert(p[i]);}// 开始补全fail指针QueueACNode queue new LinkedList();// 处理第一层ACNode root this.root.root;for(int i0;i26;i){if(root.children[i]!null){root.children[i].failroot;queue.offer(root.children[i]);}}// BFSwhile (!queue.isEmpty()){ACNode current queue.poll();for(int i0;i26;i){ACNode child current.children[i];if(child!null){queue.offer(child);// 调用迭代查找ACNode fail current.FindFail(i);if(failnull){child.failroot;}else {child.failfail.children[i];// 将最长后缀的exist数组继承过来child.AddExist(fail.children[i].exist);}}}}}/*** 匹配T串*/public void query(String T){if(Tnull||T.length()0)return;ACNode current this.root.root;for(int i0;iT.length();i){char ch T.charAt(i);int it ch-a;while (current.fail!nullcurrent.children[it]null){currentcurrent.fail;}if(current.children[it]!null){current current.children[it];}else{continue;}if(current.exist.size()0){for(int j0;jcurrent.exist.size();j){int l current.exist.get(j);if(i-l10){System.out.print(Error: i-l0!);continue;}String str T.substring(i-l1,i1);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
