2015 HN Training 7.7 B（AC自动机）

发表于 |
字数统计: 537字 | 阅读时长 ≈ 3min

B

问题描述

这里写图片描述
样例输入
3 10
AT
TT
AAAAA
3 10
ATT
TT
AAAAA

样例输出

No
Yes

提示

这里写图片描述

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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");
	}
}