您现在的位置是：课程
数据结构与算法之精妙的AC自动机【料视出品】
2023-06-30 22:21课程 人已围观
一种多模式串匹配算法，该算法在1975年产生于贝尔实验室，是著名的多模式匹配算法之一。
简单的说，KMP用来在一篇文章中匹配一个模式串；但如果有多个模式串，需要在一篇文章中把出现过的模式串都匹配出来，就需要Aho-Corasick automaton算法了。
在KMP算法中，匹配单个字符的时候，我们只需要按照文本线性的扫一遍，然后中途失配的时候，next数组会引导k回溯到正确的位置进行下一步的匹配。
但是多个模式串的时候要怎么匹配呢？Trie树不就是一个多模式的匹配吗，如果我们将KMP和Trie数结合起来，是不是会有意想不到的效果呢？
有了这些思考，AC自动机算法就这样产生了。
在AC自动机中，我们首先将每一个模式串插入到Trie树中去，建立一棵Trie树，然后构建fail指针，fail指针，顾名思义，就是当匹配失败的时候，用来引导k回溯的一个插穿在Trie树的各个节点之间的一些指针，就和KMP算法中的next数组是一样的道理。
下面贴出完整代码：
public class AhoCorasickAutomaton {
private Node root;
private List<String> target;
private HashMap<String, List<Integer>> result;
private static class Node{
String str;
Node[] table = new Node[128];
Node fail;
}
public AhoCorasickAutomaton() {
root = new Node();
}
private void buildTrietree(List<String> target){
this.target = target;
for (String str:target) {
Node curr = root;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if(curr.table[ch] == null) curr.table[ch] = new Node();
curr = curr.table[ch];
}
curr.str = str;
}
}
private void buildAC(List<String> target){
buildTrietree(target);
LinkedList<Node> queue = new LinkedList<Node>();
for(Node node:root.table){
if(node != null){
node.fail = root;
queue.addLast(node);
}
}
while (!queue.isEmpty()){
Node parent = queue.poll();
for(int i = 0;i <parent.table.length ;i++){
if(parent.table[i] != null){
queue.addLast(parent.table[i]);
Node failNode = parent.fail;
for(;;){
if(failNode == null){
break;
}
if(failNode.table[i] != null){
parent.table[i].fail = failNode.table[i];
break;
}else failNode = failNode.fail;
}
}
}
}
}
private HashMap<String ,List<Integer>> findTarget(String text){
HashMap<String, List<Integer>> result = new LinkedHashMap<String, List<Integer>>();
for(String str:target){
result.put(str, new LinkedList<Integer>());
}
Node curr = root;
int i = 0;
while (i<text.length()){
char ch = text.charAt(i);
if(curr.table[ch] != null){
curr = curr.table[ch];
if(curr.str != null)result.get(curr.str).add(i - curr.str.length() +1);
if(curr.fail != null && curr.fail.str != null)
result.get(curr.fail.str).add(i - curr.fail.str.length() + 1);
i++;
}else{
curr = curr.fail;
if(curr == null){
curr = root;
i++;
}
}
}
return result;
}
public static void main(String[] args) {
List<String> target = new ArrayList<String>();
target.add("abcdef");
target.add("abhab");
target.add("bcd");
target.add("cde");
target.add("cdfkcdf");
String text = "bcabcdebcedfabcdefababkabhabk";
AhoCorasickAutomaton aca = new AhoCorasickAutomaton();
aca.build_AC_FromTrie(target);
HashMap<String, List<Integer>> result = aca.findTarget(text);
for (Entry<String, List<Integer>> entry : result.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
}
}
