C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 716K, 提交时间: 2022-09-17 23:10:08

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4+10;
int tr[N][2],st[N],idx;
int q[N],fail[N];
int n;
char s[N];
int vs[N];
void insert()
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'0';
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
    st[u]=1;
}
void build()
{
    int hh=0,tt=0;
    for(int i=0;i<2;i++)
        if(tr[0][i])q[tt++]=tr[0][i];
    while(hh!=tt)
    {
        int t=q[hh++];
        for(int i=0;i<2;i++)
        {
            int u=tr[t][i];
            if(!u)tr[t][i]=tr[fail[t]][i];
            else
            {
                fail[u]=tr[fail[t]][i];
                q[tt++]=u;
                st[u]|=st[fail[u]];
            }
        }
    }
}
bool dfs(int u)
{
    if(vs[u]==1)return true;
    else if(vs[u]==-1)return false;

    vs[u]=1;
    for(int i=0;i<2;i++)
    {
        if(!st[tr[u][i]]&&dfs(tr[u][i]))return true;
    }
    vs[u]=-1;
    return false;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert();
    }
    build();
    if(dfs(0))puts("TAK");
    else puts("NIE");
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 784K, 提交时间: 2023-05-13 20:18:43

#include<bits/stdc++.h>
using namespace std;
const int N=30007;
int n,m,t[N][2],cnt,ne[N],tag[N],tot,tt[N],v[N],vv[N];
string s;
void add(){
	int p=0,len=s.size();
	for(int i=0;i<len;i++){
		int j=s[i]-'0';
		if(!t[p][j])t[p][j]=++cnt;
		p=t[p][j];
	}
	tag[p]=1;
}
void kmp(){
	queue<int>q;
	for(int i=0;i<2;i++)if(t[0][i])q.push(t[0][i]);
	while(!q.empty()){
		int p=q.front();
		q.pop();
		tt[++tot]=p;//拓扑序 
		for(int i=0;i<2;i++){
			int j=t[p][i],v=t[ne[p]][i];
			if(j){
				ne[j]=v;
				q.push(j);
				tag[j]|=tag[v];
			}
			else t[p][i]=v;
		}
	}
}
void dfs(int x){
	if(v[x]){
		cout<<"TAK";
		exit(0);
	}
	if(vv[x])return;
	v[x]=1;
	vv[x]=1;
	if(!tag[t[x][0]])dfs(t[x][0]);
	if(!tag[t[x][1]])dfs(t[x][1]);
	v[x]=0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		add();
	}
	kmp();
	dfs(0);
	cout<<"NIE";
}