Solution - P2444 [POI 2000] 病毒

警示后人：TLE on Hack 1

Hootime
发表于 2026-02-06 19:28

请不要重复搜索一个节点，除非你想被卡成指数。

---

ACAM 是拿来干什么的。显然是拿来多模匹配的。

那么如何做到在不是指数的时间内匹配所有可能的串？对 ACAM dfs 就好了。

#include <bits/stdc++.h>
#define llong long long
#define N 30004
using namespace std;char a[N];
int son[N][2], fail[N], tag[N], vis[N], hrdvis[N], tsiz = 1;
int n, l;int que[N], he, ta;inline bool dfs(int x){hrdvis[x] = vis[x] = true;for(int i = 0; i <= 1; ++i){if(tag[son[x][i]]) continue;;if(vis[son[x][i]] || (!hrdvis[son[x][i]]&&dfs(son[x][i]))) return true;}vis[x] = false;return false;
}int main(){scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%s", a+1), l = strlen(a+1);int x = 1;for(int i = 1; i <= l; ++i){if(!son[x][a[i]^48]) son[x][a[i]^48] = ++tsiz;x = son[x][a[i]^48];}tag[x] = true;}he = 1, ta = 0;for(int i = 0; i <= 1; ++i){if(son[1][i]) fail[son[1][i]] = 1, que[++ta] = son[1][i];else son[1][i] = 1;}while(he <= ta){int x = que[he++];tag[x] |= tag[fail[x]];for(int i = 0; i <= 1; ++i){if(son[x][i]) fail[son[x][i]] = son[fail[x]][i], que[++ta] = son[x][i];else son[x][i] = son[fail[x]][i];}}puts(dfs(1) ? "TAK" : "NIE");return 0;
}