本文共 1223 字，大约阅读时间需要 4 分钟。
如果存在一个无限长的串
所以构建\(AC\)自动机
#include #include #include #include #include #include #include #include #include #include using namespace std;#define MAX 50000struct Node{ int vis[2]; int fail,lt;}t[MAX];int n,tot;char ch[MAX];void insert(char *s){ int l=strlen(s+1),now=0; for(int i=1;i<=l;++i) { if(!t[now].vis[s[i]-48]) t[now].vis[s[i]-48]=++tot; now=t[now].vis[s[i]-48]; } t[now].lt=1;}void Getfail(){ queue Q; for(int i=0;i<2;++i) if(t[0].vis[i])Q.push(t[0].vis[i]); while(!Q.empty()) { int u=Q.front();Q.pop(); t[u].lt|=t[t[u].fail].lt; for(int i=0;i<2;++i) if(t[u].vis[i]) t[t[u].vis[i]].fail=t[t[u].fail].vis[i],Q.push(t[u].vis[i]); else t[u].vis[i]=t[t[u].fail].vis[i]; }}bool vis[MAX];bool vv[MAX];void DFS(int u){ if(t[u].lt)return; if(vis[u]){puts("TAK");exit(0);} if(vv[u])return; vis[u]=true;vv[u]=true; for(int i=0;i<2;++i) if(t[u].vis[i]) DFS(t[u].vis[i]); vis[u]=false;}int main(){ scanf("%d",&n); while(n--) { scanf("%s",ch+1); insert(ch); } Getfail(); DFS(0); puts("NIE"); return 0;}
转载于:https://www.cnblogs.com/cjyyb/p/8333831.html