本文主要是介绍2015 HN Training 7.7 B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
时间限制 : 3000 MS 空间限制 : 64 MB
样例输入
3 10
AT
TT
AAAAA
3 10
ATT
TT
AAAAA
样例输出
No
Yes
题解
这道题的官方数据相当水，有80%的数据的L都小于等于10……
AC自动机板题。把AC自动机看成一张有向图，在上面跑深搜，当深度不小于L或出现环时就可行。判环的操作类似于Tarjan……
代码
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const ll maxn=1050000;
ll s,l,tot,val[maxn],dep[maxn],fail[maxn],trie[maxn][2];
bool ins[maxn];
char c[10005];
ll id(char x)
{return x=='A'?0:1;
}
void insert()
{ll p=0,len=strlen(c+1);for(ll i=1;i<=len;i++){ll t=id(c[i]);if(!trie[p][t]) trie[p][t]=++tot;p=trie[p][t];}val[p]++;
}
void getfail()
{queue<ll> q;for(ll i=0;i<=1;i++)if(trie[0][i]) q.push(trie[0][i]);while(!q.empty()){ll x=q.front();q.pop();for(ll i=0;i<=1;i++)if(!trie[x][i]) trie[x][i]=trie[fail[x]][i];else{q.push(trie[x][i]);fail[trie[x][i]]=trie[fail[x]][i];val[trie[x][i]]+=val[fail[trie[x][i]]];}}
}
bool Tarjan(ll x)
{if(ins[x]||dep[x]>=l) return true;ins[x]=true;for(ll i=0;i<=1;i++)if(trie[x][i]&&!val[trie[x][i]]){dep[trie[x][i]]=dep[x]+1;if(Tarjan(trie[x][i])) return true;}ins[x]=false;return false;
}
int main()
{while(scanf("%lld%lld",&s,&l)==2){tot=0;for(ll i=1;i<=s;i++) scanf("%s",c+1),insert();getfail();if(Tarjan(0)) puts("Yes");else puts("No");for(ll i=0;i<=tot;i++) fail[i]=val[i]=dep[i]=fail[i]=trie[i][0]=trie[i][1]=ins[i]=0;}return 0;
}这篇关于2015 HN Training 7.7 B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
