1. 题目

传送门= ̄ω ̄=

2. 题解

AC自动机模板题
其实AC自动机就是在trie树上跑kmp。。。
一开始为了追求代码短写递归,结果不知道怎么的不停地WA。。。
调一晚上放弃了,老老实实地打了bfs版的。。。
于是很快就AC

真是气人!

推荐一篇AC自动机的博客:
http://blog.csdn.net/niushuai666/article/details/7002823

还有一个AC自动机的讲解视屏(bilibili上的):
https://www.bilibili.com/video/av6295004/

哦对了,还有我的代码:

#include <bits/stdc++.h>
#define cls(a) (memset((a),0,sizeof(a)))
using namespace std;
int t,n,nxt[500005][26],e[500005],fail[500005],cnt,ans;
char s[1000005];
queue<int> que;
void insert()
{
    int l=strlen(s),p=1;
    for(int i=0,tem;i<l;i++)
    {
        tem=s[i]-'a';
        if(!nxt[p][tem])nxt[p][tem]=++cnt;
        p=nxt[p][tem];
    }
    e[p]++;
}
void init()
{
    que.push(1);
    while(!que.empty())
    {
        for(int i=0,j;i<26;i++)
            if(nxt[que.front()][i])
            {
                j=fail[que.front()];
                while(!nxt[j][i])j=fail[j];
                fail[nxt[que.front()][i]]=nxt[j][i],que.push(nxt[que.front()][i]);
            }
        que.pop();
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),cls(nxt),cls(e),cls(fail),cnt=1,ans=0;
        for(int i=1;i<=n;i++)scanf("%s",s),insert();
        for(int i=0;i<26;i++)nxt[0][i]=1;
        init(),scanf("%s",s);
        for(int i=0,j=1,l=strlen(s);i<l;i++)
        {
            while(!nxt[j][s[i]-'a'])j=fail[j];
            j=nxt[j][s[i]-'a'];
            for(int k=j;k&&e[k]!=-1;k=fail[k])ans+=e[k],e[k]=-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

boshi · 2017年6月17日 1:27 下午

我170行

    konnyakuxzy · 2017年6月17日 3:31 下午

    Orz170行AC自动机太强啦!您代码能力太强啦Orz%%%%%%%

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *