数算实习 躲不开的病毒 Trie图

病毒 Trie图"/>

数算实习 躲不开的病毒 Trie图

躲不开的病毒

描述
有若干种病毒，每种病毒的特征代码都是一个01串。
每个程序也都是一个01串。
问是否存在不被病毒感染（不包含任何病毒的特征代码）的无限长的程序。

输入
第一行是整数n，表示有n个病毒
接下来n行，每行是一个由 0,1构成的字符串，表示一个病毒特征代码
所有的病毒的特征代码总长度不超过30000
输出
如果存在无限长的没有被病毒感染的程序，输出 “TAK”，否则输出"NIE"

样例输入
样例1:
2
10
11
样例2:
2
1
0
样例输出
样例1:
TAK
样例2:
NIE

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <deque>
using namespace std;int ncount = 2;
struct ncode
{ncode* child[2];bool isdanger;bool iscovered;ncode* pprev;ncode(){for (int i = 0; i < 2; i++)child[i] = 0;pprev = NULL;isdanger = 0;iscovered = 0;}
};
ncode tree[30002];
void buildtree(ncode* root, string s)
{int l = s.size();for (int i = 0; i < l; i++){if (root->child[s[i] - '0'] == NULL){root->child[s[i] - '0'] = tree + ncount;ncount++;}root = root->child[s[i] - '0'];}root->isdanger = 1;
}
void insertprev()
{for (int i = 0; i < 2; i++){tree[0].child[i] = tree + 1;}tree[1].pprev = tree;deque<ncode*> q;q.push_back(tree + 1);while (!q.empty()){ncode* cur = q.front();q.pop_front();for (int i = 0; i < 2; i++){ncode* curchild = cur->child[i];if (curchild != NULL){curchild->pprev = cur->pprev;while (curchild->pprev->child[i] == NULL)curchild->pprev = curchild->pprev->pprev;curchild->pprev = curchild->pprev->child[i];if (curchild->pprev->isdanger == 1)curchild->isdanger = 1;q.push_back(curchild);}}}
}
int flag = 0;
void search(ncode* root)
{if (flag == 1)return;if (root->isdanger == 1)return;if (root->iscovered == 1){flag = 1;return;}root->iscovered = 1;for (int i = 0; i < 2; i++){if (root->child[i] != NULL){search(root->child[i]);}else{ncode* pre = root->pprev;while (pre->child[i] == NULL)pre = pre->pprev;search(pre->child[i]);}}root->iscovered = 0;
}int main()
{int n;string s[30002];cin >> n;for (int i = 0; i < n; i++){cin >> s[i];buildtree(tree + 1, s[i]);}insertprev();search(tree + 1);if (flag == 1)cout << "TAK" << endl;elsecout << "NIE" << endl;return 0;
}