题解 P3796 【【模板】AC自动机（加强版）】

· · 题解

还是属于AC自动机的裸题。而AC自动机的裸题，先把模板打好后，基本上改的就是对标记点的处理。

这里就是对AC自动标记点处理的简单修改，即把匹配到的标记点都计数一下，然后求计数最大的那些标记点就行了。

还是不太不懂AC自动记得萌新们可以戳：http://blog.csdn.net/no1\_terminator/article/details/77725530

讲的非常清楚哟！

这里就简单的讲一下吧：

f[u]=v表示从根到u号节点的这个字符串的某个后缀与从根到v号节点的这个字符串是等效的（即完全相等的）

last[u]=v表示从u开始不断沿着失配边跳到的第一个是标记点的端点v，那么我们再匹配是就无需沿着f跳，而是沿着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]]。

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

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define reset(a) memset((a),0,sizeof((a)))
#define REP(i,a,b) for (int i=(a);i<=(b);i++)
using namespace std;
const int N=1e6+10;
const int M=151*71;
char s[151][71];
char T[N];
int m;
struct Aho_Corasick_Automaton{
    int NodeCnt,f[M],ch[M][26],cnt[M],val[M],last[M];
    void clear(){
        reset(f);reset(ch);reset(cnt);reset(val);reset(last);
        NodeCnt=0;
    }
    void insert(char *s,int index){
        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]=index;
    }
    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;}
                f[v]=u?ch[k][c]:0;
                last[v]=val[f[v]]?f[v]:last[f[v]];
                Q.push(v);
            }
        }
    }
    void query(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])cnt[val[u]]++;
            int v=last[u];
            while (v){
                if (val[v])cnt[val[v]]++;
                v=last[v];
            }
        }
        REP(i,1,m)res=max(res,cnt[i]);
        printf("%d\n",res);
        REP(i,1,m)if (cnt[i]==res)printf("%s\n",s[i]);
        return;
    }
}AC;
int main(){
    while (scanf("%d",&m)==1 && m){
        AC.clear();
        REP(i,1,m){
            scanf("%s",s[i]);
            AC.insert(s[i],i);
        }
        AC.getFail();
        scanf("%s",T);
        AC.query(T);
    }
    return 0;
}