2015 HN Training 7.7 B（AC自动机）

B

问题描述

样例输入
3 10
AT
TT
AAAAA
3 10
ATT
TT
AAAAA

样例输出

No
Yes

提示

---

构造一个串不含某些给定串，考虑将给定串构造AC自动机，并将其改造成有限状态自动机（每个点不存在的转移改成fail树上第一个该转移），将串结尾的标记沿着fail树传上去，然后如果自动机的转移中存在环，那么一定有解，否则
该图为DAG，求出从根节点出发的最长路（不能经过串结尾），最长路长度就是能构造出串的最大长度。
复杂度O(∑|s|)$O(\sum |s|)$

---

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define ll long long
#define N 1200005
using namespace std;
char s[N];
ll m,Max,dep[N];
int n,son[N][2],fail[N],exi[N],tot,rt;
bool Instack[N],mark[N];
void Ins()
{
    int i,p=rt,t,l=strlen(s);
    for(i=0;i<l;i++)
    {
        t=s[i]=='A'?0:1;
        if(!son[p][t])son[p][t]=++tot;
        p=son[p][t];
    }
    exi[p]=1;
}
void Build()
{
    int i,p=rt;queue<int>Q;
    for(i=0;i<2;i++)
    if(son[p][i])fail[son[p][i]]=p,Q.push(son[p][i]);
    else son[p][i]=p;
    while(Q.size())
    {
        p=Q.front();Q.pop();
        for(i=0;i<2;i++)
        if(son[p][i])
        {
            fail[son[p][i]]=son[fail[p]][i];Q.push(son[p][i]);
            exi[son[p][i]]|=exi[fail[son[p][i]]];
        }
        else son[p][i]=son[fail[p]][i];
    }
}
bool DFS(int x)
{
    Instack[x]=1;mark[x]=1;dep[x]=0;
    for(int i=0;i<2;i++)
    {
        int p=son[x][i];
        if(exi[p])continue;
        if(Instack[p])return 1;
        if(!mark[p]&&DFS(p))return 1;
        dep[x]=max(dep[x],dep[p]+1);
    }
    Max=max(Max,dep[x]);
    Instack[x]=0;return 0;
}
int main()
{
    int i,j,k,x,y;
    while(scanf("%d%lld",&n,&m)!=EOF)
    {
        tot=rt=1;Max=0;
        memset(son,0,sizeof(son));
        memset(fail,0,sizeof(fail));
        memset(exi,0,sizeof(exi));
        memset(mark,0,sizeof(mark));
        memset(Instack,0,sizeof(Instack));
        for(i=1;i<=n;i++)scanf("\n%s",s),Ins();
        Build();Max=0;
        if(DFS(rt))puts("Yes");
        else if(Max>=m)puts("Yes");
        else puts("No");
    }
}