P2444 [POI2000] 病毒

~~AC自动机~~ 询问是否存在无限长的不含目标串的字符串 试想一下，如果把这个无限长的字符串插入到AC自动机中，会发生什么？ 没错，我们永远不会跳到目标串结尾的位置（在自动机里转圈圈~~） 所以最终任务变成：在fail树上寻找一个环，使其上不包含危险节点（即不包含目标串结尾的节点），并且从根节点0可以到达这个环 因此在getfail指针的过程中，需要把危险节点的标记传递到它的子节点 然后就可以从根节点开始dfs，一旦找到环，就说明存在无限长的字符串，直接退出 注意这里要开两个数组，一个是访问标记，用来找环 一个是历史访问的记录，在dfs的时候不递归历史访问过且不在搜索栈中的节点 %一%夫哥 @beretty ```cpp #include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #include<algorithm> using namespace std; const int N=3e4+5; int n; char s[N]; struct Aho_Corasick_automation { int ch[N][2],val[N],fail[N],cnt; bool vis[N],f[N]; inline void insert(char *s) { int len=strlen(s+1),u=0; for (int i=1;i<=len;i++) { int v=s[i]-'0'; if (!ch[u][v]) ch[u][v]=++cnt; u=ch[u][v]; } ++val[u]; } inline void getfail() { queue<int>q; for (int i=0;i<2;i++) { int v=ch[0][i]; if (v) q.push(v); } while (!q.empty()) { int u=q.front(); q.pop(); for (int i=0;i<2;i++) { int v=ch[u][i]; if (v) { q.push(v); fail[v]=ch[fail[u]][i]; val[v]|=val[ch[fail[u]][i]]; } else ch[u][i]=ch[fail[u]][i]; } } } void dfs(int k) { vis[k]=1; for (int i=0;i<2;i++) { int v=ch[k][i]; if (vis[v]) { puts("TAK"); exit(0); } if (!val[v]&&!f[v]) { f[v]=1; dfs(v); } } vis[k]=0; } }AC; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%s",s+1); AC.insert(s); } AC.getfail(); AC.dfs(0); puts("NIE"); return 0; } ```