题目描述
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
1.在文本文件WIR.IN中读入病毒代码；
2.判断是否存在一个无限长的安全代码；
3.将结果输出到文件WIR.OUT中。
输入格式
在文本文件WIR.IN的第一行包括一个整数n(n\le 2000)(n≤2000)，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
输出格式
在文本文件WIR.OUT的第一行输出一个单词：
TAK——假如存在这样的代码；
NIE——如果不存在。
输入输出样例
输入
3
01
11
00000
输出
NIE
分析
想办法让那串无限长的字符串不断的在树上失配，然后不断的走fail指针最后进入一个循环即可
即在树上dfs，保证不经过任何字符串尾节点使得找到一个树上环
AC code
#include <bits/stdc++.h>
using namespace std;
/*
* AC 自动机：多个模式串去匹配一个串，求有多少个模式串与主串有匹配内容
*
* 使用操作：
* 1、把每一个模式串插入到树中 insert
* 2、build
* 3、使用 query 询问有多少个模式串匹配
*/
const int CHAR_NUM = 2;//仅小写
const int MAXN = 2100;//模式串个数
const int MAXM = 30100;//模式串最长长度
const int NUM = MAXN * MAXM;//空间=个数*长度，稳
struct Trie {
int c[NUM][CHAR_NUM], val[NUM], fail[NUM], cnt;
void insert(char *s) {
int len = strlen(s);
int now = 0;
for (int i = 0; i < len; i++) {
// int v = s[i] - 'a';
int v = s[i] - '0';
if (!c[now][v])c[now][v] = ++cnt;
now = c[now][v];
}
val[now]++;
}
void build() {
queue<int> q;
for (int i = 0; i < CHAR_NUM; i++)if (c[0][i])fail[c[0][i]] = 0, q.push(c[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < CHAR_NUM; i++)
if (c[u][i])fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);
else c[u][i] = c[fail[u]][i];
}
}
int query(char *s) {
int len = strlen(s);
int now = 0, ans = 0;
for (int i = 0; i < len; i++) {
// now = c[now][s[i] - 'a'];
now = c[now][s[i] - '0'];
for (int t = now; t && ~val[t]; t = fail[t])ans += val[t], val[t] = -1;
}
return ans;
}
} AC;
char s[30100];
bool vis[NUM];
bool dfs(int cur) {
for (int i = 0; i < CHAR_NUM; ++i) {
int x = AC.c[cur][i];
if (!AC.val[x]) {
bool flag = false;
int t = x;
while (t) {
if (AC.val[t]) {
flag = true;
break;
}
t = AC.fail[t];
}
if (flag)
continue;
if (vis[x])
return true;
vis[x] = true;
if (dfs(x)) {
return true;
}
vis[x] = false;
}
}
return false;
}
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> s;
AC.insert(s);
}
AC.build();
vis[0] = true;
bool flag = dfs(0);
if (flag) {
cout << "TAK" << endl;
} else {
cout << "NIE" << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
long long test_index_for_debug = 1;
char acm_local_for_debug;
while (cin >> acm_local_for_debug) {
cin.putback(acm_local_for_debug);
if (test_index_for_debug > 20) {
throw runtime_error("Check the stdin!!!");
}
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
}
#else
solve();
#endif
return 0;
}