猫史档案馆

【爵士精品】字符串算法：AC自动机【无情的AC自动机勿喷（我也知道不会喷）】

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入格式 第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式

一个数表示答案

你当然可以喵，不过这是喵分。

 

AC自动机=Trie+KMP

两个优化：

1.类似并差集的路径压缩，把不存在的ch[u][c]全部指向ch[f[u]][c]（f是失配函数）

2.把有效失配函数用last指针保存。

这里就简单的讲一下：

我们重新定义KMP中的失配函数。

设f[u]=v表示从根到u号节点的这个字符串的某个后缀与从根到v号节点的这个字符串是等效的（即完全相等的）！这个后缀必须是尽量地长。

我们匹配到在一个模式串的时候就不断的沿着失配边跳，所有的端点v是标记点的失配边都对应了一个模式串。

但是这个失配关系往往会非常复杂，即我们跳了很多次，但是没有一个端点是标记点，所以我们引入last指针的优化。

即定义last[u]=v表示从u开始不断沿着失配边跳到的第一个是标记点的端点v，那么我们再匹配是就无需沿着f跳，而是沿着last跳，没跳到一个last，它就一定对应一个模式串，所以效率是非常高的。

我们首先考虑f的递推。我们设当前节点为u，其一个孩子ch[u][c]=v，k表示u沿着f边跳一次对应的点，即k=f[u],

那么如果u不是根节点，f[v]=ch[k][c]，即沿着k再向下走一个c字符，这时两个字符串还是相等的对不对。

如果u是根节点那就没什么好说的了，f[v]=0。

在此条件下，last就非常好递推了，,那么如果f[v]是标记点，那么last[v]=f[v],

否则last[v]=last[f[v]]。

这个f[v]并不能保证ch[k][c]就一定存在，所以还需要一个while循环一直跳直到找到一个ch[k][c]!=0的端点。可以出现了一个while，既使代码不够优美，又使效率无法保证，所以我们直接把所有ch[k][c]=0的端点的ch[k][c]直接连向ch[f[k]][c]，就好像并差集的一个路径压缩，由于Trie是读完所有模式串后建的，所以这个加边并不会影响Trie。

考虑到这是一个Trie树上的递推，所以我们用BFS搞一搞就好了。

参考代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REP(i,a,b) for (int i=(a);i<=(b);i++)
#define reset(a) memset((a),0,sizeof((a)))
using namespace std;
const int N=1e6+10;
char P[N];
int n;
struct Aho_Corasick_Automaton{
    int ch[N][26],val[N],f[N],last[N],NodeCnt;
    void clear(){
        reset(ch);reset(val);reset(f);reset(last);
        NodeCnt=0;
    }
    void insert(char *S){
        int u=0,n=strlen(S);
        REP(i,0,n-1){
            int c=S[i]-'a';
            if (!ch[u][c])ch[u][c]=++NodeCnt;
            u=ch[u][c];
        }
        val[u]++;
    }
    void getFail(){
        queue<int> Q;
        Q.push(0);
        while (!Q.empty()){
            int u=Q.front(),k=f[u];Q.pop();
            REP(c,0,25){
                int v=ch[u][c];
                if (!v){ch[u][c]=ch[k][c];continue;}
                Q.push(v);
                f[v]=u?ch[k][c]:0;
                last[v]=val[f[v]]?f[v]:last[f[v]];
            }
        }
    }
    int count(char *T){
        int u=0,n=strlen(T),res=0;
        REP(i,0,n-1){
            int c=T[i]-'a';
            u=ch[u][c];
            if (val[u])res+=val[u],val[u]=0;
            int v=u;
            while (last[v]){
                v=last[v];
                if (val[v])res+=val[v],val[v]=0;
            }
        }
        return res;
    }
}AC;
int main(){
    scanf("%d",&n);
    AC.clear();
    REP(i,1,n){
        scanf("%s",P);
        AC.insert(P);
    }
    AC.getFail();
    scanf("%s",P);
    printf("%d\n",AC.count(P));
    return 0;
}

最后送上一首神曲：

Come and Get Your Love，红骨头乐队主唱，电影《银河护卫队》插曲。
歌词
Hail （hail）, what's the matter with your head, yeah
　　Hail （hail）, what's the matter with your mind and your sign?
　　And-a ooh-ohh
　　Hail （hail）, nothin's a matter with your head, baby, find it
　　Come on and find it
　　Hail, with it, baby, cause you're fine and you're mine
　　And you look so divine
　　Come and get your love
　　Come and get your love
　　Come and get your love
　　Come and get your love
　　Hail （hail）, what's the matter with your feel right?
　　Don't you feel right, baby?
　　Hail, oh yeah, get it from the main vine, alright
　　I said-a find it, find it, darling, love it if you like it, yeah
　　Hail （hail）, it's your business if you want some
　　Take some, get it together baby
　　Come and get your love
　　Come and get your love
　　Come and get your love
　　Come and get your love
　　Come and get your love, come and get your love
　　Come and get your love now
　　Come and get your love, come and get your love
　　Come and get your love now
　　（Repeat）
　　Come and get your love
　　Come and get your love
　　Come and get your love
　　Come and get your love
　　Hail （hail）, what's the matter with your feel right?
　　Don't you feel right, baby?
　　Hail, oh yeah, get it from the main vine, alright
　　La, la, la.... （come and get your love）
　　La, la, la.... （come and get your love）
　　La, la, la.... （come and get your love）
　　La, la, la.... （come and get your love）
　　La, la, la.... （come and get your love）
　　La, la, la....
中文词
是的是的(嘿是的)
怎么了你的头(哦)
是的是的(嘿是的)
怎么了你的思想和你的星座,哦耶
我要如何得到它,孩子会得到我的爱吗636f70797a喵31333337373638?
和我说话告诉我我要怎样得到它
纯威士忌酒
我为你准备好宝贝,准备好了对你的爱
别让我等待因为我真的需要它
是的是的(嘿是的)
与婴儿因为你的好和我的,和你看起来很神圣
来得到你的爱,来得到你的爱(来得到你的爱)
来得到你的爱,哇哦,来得到你的爱
是啊,是啊(嘿是的)
怎么了你感觉对的,你不觉得对孩子
是的是的是的是的是的是的)
从主线,好吧
我要如何得到它,孩子会得到我的爱吗?
和我说话告诉我我要怎样得到它
我为你准备好宝贝,准备好了对你的爱
别让我等待因为我真的需要它
是的是的(嘿是的)
这是你的业务,如果你想要一些,
带一些,把它在一起的婴儿
来得到你的爱,来得到你的爱,来得到你的爱了
来得到你的爱,来得到你的爱,来得到你的爱了
Whutcha等待因为我准备好了你的爱
快点把它得到它如果你想要它
怎么了,有什么问题
很容易在一起,我们会解决它