本文共 1699 字，大约阅读时间需要 5 分钟。
将所有串加入AC自动机
如果某个节点是终点或者对应的fail节点是终点，那么将这个点删去
最后存在环说明可以构造出无限长的01序列
#include#include using namespace std;queue q;char str[30005];int ok, cnt, tre[80005][2], End[80005], fail[80005], vis[80005], ins[80005];void Insert(char *str){ int i, p = 1; for(i=1;str[i]!='\0';i++) { if(tre[p][str[i]-'0']==0) tre[p][str[i]-'0'] = ++cnt; p = tre[p][str[i]-'0']; } End[p] = 1;}void Sech(int u){ int v, i; ins[u] = vis[u] = 1; for(i=0;i<=1;i++) { v = tre[u][i]; if(ins[v]) ok = 1; if(vis[v] || End[v]) continue; Sech(v); } ins[u] = 0;}void ACmach(){ int i, now, p; fail[1] = 0; q.push(1); while(q.empty()==0) { now = q.front(); q.pop(); for(i=0;i<=1;i++) { if(tre[now][i]==0) { tre[now][i] = tre[fail[now]][i]; continue; } p = fail[now]; while(tre[p][i]==0) p = fail[p]; fail[tre[now][i]] = tre[p][i]; if(End[tre[p][i]]) End[tre[now][i]] = 1; q.push(tre[now][i]); } }}int main(void){ int n, i; scanf("%d", &n); tre[0][0] = tre[0][1] = cnt = 1; for(i=1;i<=n;i++) { scanf("%s", str+1); Insert(str); } ACmach(); Sech(1); if(ok) printf("TAK\n"); else printf("NIE\n"); return 0;}/*51110001010110110001*/
转载地址：http://tmmgf.baihongyu.com/