多模式串匹配——ac自动机

简单来说，ac自动机实际上就是把trie树和kmp的思想结合到了一起。在使用一个主串去匹配多个模式串这种应用场景，如果当前节点失配，不用重新在根节点开始匹配，多了一个fail指针，就像kmp失配时用到的next数组一样，这样就可以提升效率了~
先是构建trie树，这里不再赘述，如果不清楚，去leetcode刷刷应该就能明白了。构建完trie树之后，就需要构建前面说的fail指针了，
fail指针的含义就是：当前节点匹配，但是没有办法向下继续匹配（另一种说法是当前节点失配），需要查看当前匹配的后缀是否有更短的模式串进行匹配，如果有，跳转到对应的节点

上代码如下：

// fail传递父子关系
q.push(root);
while(!q.empty()){
    cur = q.top();q.pop();
    for(int i=0; i<26;i++){
        // child入队列并且设置child的fail
        child = cur->child[i];
        if(child==NULL) continue;
        if(cur==root)child->fail=root;
        else{
            q = cur->fail;
            while(q){
                if(q->child[i]!=NULL){
                    child->fail = q->child[i];
                    break;
                }
                q=q->fail;
            }
            if(q==NULL) child->fail=root;
        }
        q.push(child);
    }
}

这段代码的核心思想就是当前节点fail已经设置，设置其下一层孩子的fail，原理就是查看当前节点的fail节点下是否有对应child[i]的节点，如果有，指过去，如果没有找到，指向root。


其匹配代码如下：

void match(char *str, int len){
    cur = root;
    for(int i=0; i<len; i++){
        int idx=str[i]-'a';
        while(cur->child[idx]==NULL && cur!==root)cur=cur->fail;
        cur = cur->child[idx];
        if(cur == NULL) cur=root;
        tmp = cur;
        // 每次匹配上一个字符，需要查看其对应的fail，以便查看是否命中了更短的模式串
        while(tmp!=root){
            if(tmp->is_leaf){
                int pos = i-tmp->length+1;
                cout<<"pos: "<<pos<<"; length:" << tmp->length<<endl;
            }
            tmp=tmp->fail;
        }
    }
}

大体思路应该都没问题，这里面需要多说一嘴的就是最后的含有tmp的循环，这层循环的含义也可以帮助理解fail指针的含义：
如果当前节点可以匹配str[i]，则有可能命中比当前更短的模式串，需要用fail指针不断的去递归调用，才能找到所有以str[i]结尾的模式串



主要参考资料：
https://www.cnblogs.com/sclbgw7/p/9260756.html