BZOJ 2938 [POI2000]病毒 (剪枝/A*迭代搜索)

LOJ BZOJ

题目大意：给你一些模式串，问是否存在一个无限长的文本串，不包含任何一个给定的模式串

并没有想到去模拟合法的文本串在模式串的Trie图上匹配的过程..我好菜啊

如果一个字符串合法，那么它的每个子串都不是任何一个模式串的结尾，即沿着Fail链跳到根的每个点都不是结尾

一个合法文本串在模式串构成的Trie图上匹配的过程中，会不断沿着一个环去跳

如果一个环合法，那么这个环需要满足环上每个点，以及根节点到第一个接触到环的路径上的每个点，都合法

找合法环的过程中，可以用类似于tarjan边双的方法，用两个数组记录那些点被访问过，以及那些点在栈中

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #define NN 30010
 6 #define ll long long 
 7 #define uint unsigned int
 8 #define ull unsigned long long 
 9 #define inf 0x3f3f3f3f
10 #define idx(x) (x-'0')
11 using namespace std;
12 
13 int n;
14 char str[NN];
15 int head[NN],nt[NN],vis[NN],use[NN],cte;
16 struct Edge{int to,nxt;}edge[NN*2];
17 void ae(int u,int v){
18     cte++;edge[cte].nxt=head[u];
19     edge[cte].to=v,head[u]=cte;
20 }
21 struct AC{
22 int fail[NN],g[NN],ch[NN][2],ed[NN],tot;
23 void Build_Trie(char *a,int len)
24 {
25     int x=0;
26     for(int i=1;i<=len;i++){
27         if(!ch[x][idx(a[i])])
28             ch[x][idx(a[i])]=++tot;
29         x=ch[x][idx(a[i])];
30     }ed[x]=1;
31 }
32 void Build_Fail()
33 {
34     queue<int>q;
35     if(ch[0][0]) q.push(ch[0][0]);
36     if(ch[0][1]) q.push(ch[0][1]);
37     while(!q.empty())
38     {
39         int x=q.front();q.pop();
40         ae(fail[x],x);
41         for(int i=0;i<2;i++){
42             if(ch[x][i]){
43                 fail[ch[x][i]]=ch[fail[x]][i];
44                 q.push(ch[x][i]);
45             }else{
46                 ch[x][i]=ch[fail[x]][i];
47             }
48         }
49     }
50     q.push(0);
51     while(!q.empty())
52     {
53         int x=q.front();q.pop();
54         for(int j=head[x];j;j=edge[j].nxt){
55             int v=edge[j].to;
56             if(ed[v]||g[x]) g[v]=1;
57             q.push(v);
58         }
59     }
60 }
61 int find_cir(int x)
62 {   
63     if(vis[x]) return 0;
64     vis[x]=1,use[x]=1;
65     int ans=0;
66     for(int i=0;i<2;i++){
67         if(use[ch[x][i]]) return 1;
68         if(!g[ch[x][i]])
69             ans=find_cir(ch[x][i]);
70         if(ans) return 1;
71     }use[x]=0;return 0;
72 }
73 void solve()
74 {
75     for(int i=1;i<=n;i++){
76         scanf("%s",str+1);
77         int len=strlen(str+1);
78         Build_Trie(str,len);
79     }Build_Fail();
80     int ans=0;
81     ans=find_cir(ch[0][0]);
82     if(ans){printf("TAK\n");return;}
83     memset(vis,0,sizeof(vis));
84     ans=find_cir(ch[0][1]);
85     if(ans){printf("TAK\n");return;}
86     printf("NIE\n");
87 }
88 }ac;
89 
90 int main()
91 {
92     //freopen("t2.in","r",stdin);
93     scanf("%d",&n);
94     ac.solve();
95     return 0;
96 }