https://www.luogu.org/problemnew/show/P2444
https://www.lydsy.com/JudgeOnline/problem.php?id=2938
题解:AC自动机
AC自动机是一种多模字符串匹配算法。构造 Trie 树 后,在模式串末尾一位的结点作上标记。平常的 AC自动机 是尽量能多接触到这些标记,使总值最大。本题倒是有点奇葩,要构造一个可行的无限长文本串,使没有任何子串为给出模式串中的一个。也就是说,我们需要让平常 AC自动机 的查询操作,尽量避免标记,能用失配指针跳转就跳转。
因为要有无限长的可行串,根据 AC自动机 的原理,我们可以将结点连接到儿子的边当作一条单向边,同时失配指针也当作一条单向边,如果存在一个环,且环上没有任何危险标记(即病毒代码段末尾一位的结点专门作的编号),此时 AC自动机 能一直在环上匹配,并且永远也不会得到为模式串的一个子串,就像程序中的死循环一样。这个找环我们可以通过 dfs 来实现。
注意事项
1 . 我们需要建立两个布尔数组,其中一个布尔数组记录每个节点在当前 dfs 走的路径上有没有被选中,另一个布尔数组记录每个节点历史上有没有被访问过。如果当前路径形成回路,就找到环了,应该还是比较好实现的。
2 . 避免危险标记,也就是说如果下一个结点拥有危险标记,就不走那个结点。
3 . 在构造失配指针时,一个很明显的优化是:如果一个结点拥有了失配指针,它指向的结点如果有危险标记,自己必然也危险,因为它到根结点形成的串是自己到根节点的后缀。
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=3e5+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
char str[N];
struct Aho_Corasick_Automaton{
int trie[N][2],val[N],fail[N],last[N],nodenum,vis[N],pre[N],d[N];
void clear(){
memset(trie,0,sizeof(trie));
memset(val,0,sizeof(val));
memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));
memset(fail,0,sizeof(fail));
memset(last,0,sizeof(last));
memset(d,0,sizeof(d));
nodenum=0;
}
void insert(char * str){
int len=strlen(str),pos=0;
for(int i=0;i<len;i++){
int ch=str[i]-'0';
if(trie[pos][ch]==0)trie[pos][ch]=++nodenum;
pos=trie[pos][ch];
}
val[pos]++;
d[pos]=1;
}
void GetFail(){
queue<int>Q;
Q.push(0);
while(!Q.empty()){
int u=Q.front(),k=fail[u];
Q.pop();
for(int ch=0;ch<=1;ch++){
int v=trie[u][ch];
if (!v){trie[u][ch]=trie[k][ch];continue;}
Q.push(v);
fail[v]=u?trie[k][ch]:0;
if(u&&d[trie[k][ch]])d[v]=1;
last[v]=val[fail[v]]?fail[v]:last[fail[v]];
}
}
}
bool DFS(int u){ // 通过搜索寻找有没有环
pre[u] = 1; // 作下路径标记
for(int i = 0 ; i <= 1 ; i++){
int v=trie[u][i];
if(pre[v]){ // 根据路径标记判断是否拥有环
return true;
}else if(!d[v] && !vis[v]){
// 只有下一位不为危险结点并且有可能成环,才递归搜索
vis[v] = 1; // 下一个结点已经被搜索过了
if(DFS(v))return true;
}
}
pre[u] = 0; // 抹除路径标记
return false;
}
}AC;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d",&n)){
AC.clear();
for(int i=1;i<=n;i++){
scanf("%s",str);
AC.insert(str);
}
AC.GetFail();
cout<<(AC.DFS(0)?"TAK":"NIE")<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}