主要思路
这道题铁定是要用 AC 自动机来进行实现的。我们把这些字符串全部通过 insert 操作放入了自动机之后,怎样改写 build_AC_automation 操作来搞定这道题呢?
首先,我们发现 fail 指针可以把整个 trie 树变成一张图(每一个点都加了一条虚边)。所以我们会发现,只要我们找到这张图的一个环,且这个环上所有的点都不是某个不安全代码的结尾点,就可以认定有无限长的代码安全。原因解析起来非常的简单,因为如果有一个这样安全的环,那么无限长的代码势必在这个环内无限循环,且因为这是安全的,所以也可以保证这一长串的代码是安全的。
详见代码。
代码
// P2444.cpp
#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int MX_N = 30020;
struct node
{
node *nxt[2], *fail;
bool sum, ins, vis;
node() { nxt[0] = nxt[1] = fail = NULL, sum = 0, ins = vis = false; }
};
node *root;
int n, longest;
void insert(string str)
{
int siz = str.length();
node *p = root;
for (int i = 0; i < siz; i++)
p = (p->nxt[str[i] - '0'] == NULL) ? (p->nxt[str[i] - '0'] = new node()) : p->nxt[str[i] - '0'];
p->sum = true;
}
void build_ac_automation()
{
queue<node *> q;
q.push(root);
while (!q.empty())
{
node *curt = q.front();
q.pop();
for (int i = 0; i < 2; i++)
if (curt->nxt[i] != NULL)
{
if (curt == root)
curt->nxt[i]->fail = root;
else
{
node *p = curt->fail;
while (p)
if (p->nxt[i] != NULL)
{
curt->nxt[i]->fail = p->nxt[i];
curt->nxt[i]->sum |= p->nxt[i]->sum;
break;
}
else
p = p->fail;
if (p == NULL)
curt->nxt[i]->fail = root;
}
q.push(curt->nxt[i]);
}
else if (curt->fail != NULL)
curt->nxt[i] = curt->fail->nxt[i];
}
}
bool dfs(node *curt)
{
if (curt->ins)
return true;
if (curt->vis || curt->sum > 0)
return false;
curt->vis = curt->ins = true;
for (int i = 0; i < 2; i++)
if (curt->nxt[i] != NULL && dfs(curt->nxt[i]))
return true;
curt->ins = false;
return false;
}
char buff[30020];
int main()
{
scanf("%d", &n);
root = new node();
for (int i = 1; i <= n; i++)
scanf("%s", buff), insert(buff);
build_ac_automation();
if (dfs(root))
printf("TAK");
else
printf("NIE");
return 0;
}
// P2444.cpp
#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int MX_N = 30020;
struct node
{
node *nxt[2], *fail;
bool sum, ins, vis;
node() { nxt[0] = nxt[1] = fail = NULL, sum = 0, ins = vis = false; }
};
node *root;
int n, longest;
void insert(string str)
{
int siz = str.length();
node *p = root;
for (int i = 0; i < siz; i++)
p = (p->nxt[str[i] - '0'] == NULL) ? (p->nxt[str[i] - '0'] = new node()) : p->nxt[str[i] - '0'];
p->sum = true;
}
void build_ac_automation()
{
queue<node *> q;
q.push(root);
while (!q.empty())
{
node *curt = q.front();
q.pop();
for (int i = 0; i < 2; i++)
if (curt->nxt[i] != NULL)
{
if (curt == root)
curt->nxt[i]->fail = root;
else
{
node *p = curt->fail;
while (p)
if (p->nxt[i] != NULL)
{
curt->nxt[i]->fail = p->nxt[i];
curt->nxt[i]->sum |= p->nxt[i]->sum;
break;
}
else
p = p->fail;
if (p == NULL)
curt->nxt[i]->fail = root;
}
q.push(curt->nxt[i]);
}
else if (curt->fail != NULL)
curt->nxt[i] = curt->fail->nxt[i];
}
}
bool dfs(node *curt)
{
if (curt->ins)
return true;
if (curt->vis || curt->sum > 0)
return false;
curt->vis = curt->ins = true;
for (int i = 0; i < 2; i++)
if (curt->nxt[i] != NULL && dfs(curt->nxt[i]))
return true;
curt->ins = false;
return false;
}
char buff[30020];
int main()
{
scanf("%d", &n);
root = new node();
for (int i = 1; i <= n; i++)
scanf("%s", buff), insert(buff);
build_ac_automation();
if (dfs(root))
printf("TAK");
else
printf("NIE");
return 0;
}
// P2444.cpp #include <iostream> #include <queue> #include <cmath> #include <cstring> #include <cstdio> using namespace std; const int MX_N = 30020; struct node { node *nxt[2], *fail; bool sum, ins, vis; node() { nxt[0] = nxt[1] = fail = NULL, sum = 0, ins = vis = false; } }; node *root; int n, longest; void insert(string str) { int siz = str.length(); node *p = root; for (int i = 0; i < siz; i++) p = (p->nxt[str[i] - '0'] == NULL) ? (p->nxt[str[i] - '0'] = new node()) : p->nxt[str[i] - '0']; p->sum = true; } void build_ac_automation() { queue<node *> q; q.push(root); while (!q.empty()) { node *curt = q.front(); q.pop(); for (int i = 0; i < 2; i++) if (curt->nxt[i] != NULL) { if (curt == root) curt->nxt[i]->fail = root; else { node *p = curt->fail; while (p) if (p->nxt[i] != NULL) { curt->nxt[i]->fail = p->nxt[i]; curt->nxt[i]->sum |= p->nxt[i]->sum; break; } else p = p->fail; if (p == NULL) curt->nxt[i]->fail = root; } q.push(curt->nxt[i]); } else if (curt->fail != NULL) curt->nxt[i] = curt->fail->nxt[i]; } } bool dfs(node *curt) { if (curt->ins) return true; if (curt->vis || curt->sum > 0) return false; curt->vis = curt->ins = true; for (int i = 0; i < 2; i++) if (curt->nxt[i] != NULL && dfs(curt->nxt[i])) return true; curt->ins = false; return false; } char buff[30020]; int main() { scanf("%d", &n); root = new node(); for (int i = 1; i <= n; i++) scanf("%s", buff), insert(buff); build_ac_automation(); if (dfs(root)) printf("TAK"); else printf("NIE"); return 0; }