【字符串】#2938. [Poi2000]病毒

分析

不难想到使用 Trie 图来模拟匹配的过程。

那么要求的就等价于：判断是否可以从 Trie 图的根节点 \(0\) 出发不经过非法节点找到一个环。

而非法节点则等价于：插入的模式串在 Trie 中对应的叶子节点 \(t\)、满足 \(fail[u]=t\) 的所有节点 \(u\)。

最后使用一遍 \(\texttt{dfs}\) 在 Trie 图上找环即可。

实现

• 在插入模式串以及建立 \(fail\) 指针时利用 \(fail\) 的关系标记非法节点。
• \(\texttt{dfs}\) 找环就是维护一个访问数组 \(vis[]\) 以及是否在栈中的数组 \(ins[]\)，然后当遇到一个点在 \(\texttt{dfs}\) 树对应的栈中的时候就返回 \(true\) 即可。

// Problem: P2444 [POI2000]病毒
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2444
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e5+5;

int n;

int tr[N][2], idx;
int fail[N];
bool ng[N];

void insert(string &s){
	int u=0;
	for(auto &c: s){
		int val=c-'0';
		int &go=tr[u][val];
		if(!go) go=++idx;
		u=go;
	}
	ng[u]=true;
}

void build(){
	queue<int> q;
	rep(c,0,1) if(tr[0][c]){
		q.push(tr[0][c]);
		fail[tr[0][c]]=0;
	}
	
	while(q.size()){
		int u=q.front(); q.pop();
		rep(c,0,1){
			int &go=tr[u][c];
			if(!go) go=tr[fail[u]][c];
			else fail[go]=tr[fail[u]][c], ng[go]|=ng[fail[go]], q.push(go);
		}
	}
}

bool vis[N], ins[N];

bool dfs(int u){
	vis[u]=ins[u]=true;
	rep(c,0,1){
		int go=tr[u][c];
		if(ins[go]) return true;
		if(ng[go] || vis[go]) continue;
		if(dfs(go)) return true;
	}
	ins[u]=false;
	return false;
}

void solve(){
	puts(dfs(0)? "TAK": "NIE");
}

signed main(){
	cin>>n;
	rep(i,1,n){
		string s; cin>>s;
		insert(s);
	}	
	build();
	
	solve();
	
	return 0;
}