考虑AC自动机匹配的过程
如果下一个节点是危险节点，我们就不跳到这个节点
如果下一个节点的 fail 是危险节点，我们也不跳到这个节点
这个标记在 getfail 的时候就可以打上
这样只要匹配的过程中能构成一个循环即可
非常的妙啊
#include#include #include #include #include #include #include using namespace std;const int MAXN = 1000005;struct Node{ int fail, nxt[2], lst; bool end; Node(){fail = lst = 0; memset(nxt, 0, sizeof(nxt));end = false;}}t[MAXN];int n, Root = 0, ptr = 0;char str[MAXN];bool getans = false, inque[MAXN], vis[MAXN];queue q;inline int newnode() { return ++ptr;}inline void Insert(char *s) { int len = strlen(s), cur = Root; for(int i = 0; i < len; ++i) { register int x = s[i] - '0'; if(!t[cur].nxt[x]) t[cur].nxt[x] = newnode(); cur = t[cur].nxt[x]; } t[cur].end = true; return;}inline void getfail() { t[Root].fail = 0; for(int i = 0; i < 2; ++i) if(t[Root].nxt[i]) q.push(t[Root].nxt[i]); while(!q.empty()) { int cur = q.front(); q.pop(); for(int i = 0; i < 2; ++i) { register int son = t[cur].nxt[i], fail = t[cur].fail; if(!son) { t[cur].nxt[i] = t[fail].nxt[i]; continue; } t[son].fail = t[fail].nxt[i]; t[son].end |= t[t[son].fail].end; q.push(son); } } return;}void dfs(int cur) { if(getans) return; inque[cur] = true; for(int i = 0; i < 2; ++i) { int son = t[cur].nxt[i]; if(inque[son]) { getans = true; break; } if(t[son].end || vis[son]) continue; vis[son] = true; dfs(son); } inque[cur] = false; return;}int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%s", str); Insert(str); } getfail(); dfs(Root); if(getans) puts("TAK"); else puts("NIE"); return 0;}