题意
给定多个01模式串,问是否存在一个无限长的字符串不包含任何一个模式串。
分析
- 好像数据有点水,网上一大堆
题解连样例都没过??? - 多模式串,先把AC自动机建出来再说。
- 反向考虑,若存在一个无限长的字符串不包含任何一个模式串,那就说明这个字符串可以在AC自动机上无限匹配,所以我们在AC自动机上dfs找环即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
bool flag;
struct ACM{
int tr[N][2],val[N],fail[N],cnt,x[N],vis[N];
void init(){
memset(tr,0,sizeof(tr));
memset(val,0,sizeof(val));
memset(fail,0,sizeof(fail));
}
void insert(char *s){
int len=strlen(s);
int now=0;
for(int i=0;i<len;i++){
int id=s[i]-'0';
if(!tr[now][id]){
tr[now][id]=++cnt;
}
now=tr[now][id];
}
val[now]++;
x[now]++;
}
void build(){
queue<int> q;
for(int i=0;i<2;i++){
if(tr[0][i]){
q.push(tr[0][i]);
fail[tr[0][i]]=0;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<2;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
x[tr[u][i]]+=x[tr[fail[u]][i]];
q.push(tr[u][i]);
}else{
tr[u][i]=tr[fail[u]][i];
}
}
}
}
void dfs(int u){
if(flag){
return;
}
vis[u]=0;
for(int i=0;i<2;i++){
int v=tr[u][i];
if(x[v]){
continue;
}
if(vis[v]==-1){
dfs(v);
}else if(vis[v]==0){
flag=true;
}
}
vis[u]=1;
}
void solve(){
memset(vis,-1,sizeof(vis));
dfs(0);
}
}ac;
int n;
char s[N];
int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
ac.init();
for(int i=0;i<n;i++){
scanf("%s",s);
ac.insert(s);
}
ac.build();
ac.solve();
if(flag){
printf("TAK\n");
}else{
printf("NIE\n");
}
return 0;
}