題意：
給出一些病毒的特征串，如果一個程序（或者將程序反轉(zhuǎn)）中出現(xiàn)了某個病毒的特征串，則該程序被這個病毒感染了。給出若干病毒串，一個程序串，問改程序被多少種病毒感染了？
解法：
比賽的時候模板有bug，WA到死，竟然這個用了數(shù)月的模板之前還神奇的通過了N道自動機的題目，不可思議。。
一道非常裸的自動機，將程序串正反匹配一遍既得答案。
自動機節(jié)點結(jié)構(gòu)如下：
1 struct node
2 {
3 unsigned long long bit[4];
4 struct node *nxt[26];
5 struct node *pre;
6 }；
用位記錄以當前節(jié)點為后綴的子串包含了多少種模式串，位壓縮策略如下：
1 void setbit(unsigned long long bit[],int pos)
2 {
3 bit[pos/64]|=(1ll<<(pos%64));
4 }
自動機轉(zhuǎn)移策略（計算前綴指針）：
1 void makepre()
2 {
3 struct node *p=buf;
4 int s=-1,e=-1,i;
5 for(i=0;i<26;i++)
6 if(p->nxt[i])
7 {
8 p->nxt[i]->pre=p;
9 q[++e]=p->nxt[i];
10 }
11 else
12 p->nxt[i]=p;
13 while(s!=e)
14 {
15 p=q[++s];
16 for(i=0;i<4;i++)
17 (p->bit[i])|=(p->pre->bit[i]);
18 for(i=0;i<26;i++)
19 {
20 struct node *pre=p->pre;
21 while(!(pre->nxt[i])) pre=pre->pre;
22 if(p->nxt[i])
23 {
24 p->nxt[i]->pre=pre->nxt[i];
25 q[++e]=p->nxt[i];
26 }
27 else
28 p->nxt[i]=pre->nxt[i];
29 }
30 }
31 }
整個程序（這次就當重新修正下模板。。用標準C語言寫下自動機）：
1 # include <stdio.h>
2 # include <stdlib.h>
3 # define N 300000
4 # define root 0
5 # include <string.h>
6 struct node
7 {
8 unsigned long long bit[4];
9 struct node *nxt[26];
10 struct node *pre;
11 }buf[N];
12 char str[5200000],tstr[5200000];
13 int c;
14 struct node *q[N];
15 void clear(struct node *pos)
16 {
17 memset(pos->bit,0,sizeof(pos->bit));
18 memset(pos->nxt,NULL,sizeof(pos->nxt));
19 pos->pre=NULL;
20 }
21 void init()
22 {
23 c=1;
24 clear(buf);
25 }
26 void setbit(unsigned long long bit[],int pos)
27 {
28 bit[pos/64]|=(1ll<<(pos%64));
29 }
30 void insert(char *str,int id)
31 {
32 int i,len=strlen(str);
33 struct node *p=buf;
34 for(i=0;i<len;i++)
35 {
36 if(!(p->nxt[str[i]-'A']))
37 {
38 p->nxt[str[i]-'A']=&buf[c++];
39 clear(p->nxt[str[i]-'A']);
40 }
41 p=p->nxt[str[i]-'A'];
42 }
43 setbit(p->bit,id);
44 }
45 void makepre()
46 {
47 struct node *p=buf;
48 int s=-1,e=-1,i;
49 for(i=0;i<26;i++)
50 if(p->nxt[i])
51 {
52 p->nxt[i]->pre=p;
53 q[++e]=p->nxt[i];
54 }
55 else
56 p->nxt[i]=p;
57 while(s!=e)
58 {
59 p=q[++s];
60 for(i=0;i<4;i++)
61 (p->bit[i])|=(p->pre->bit[i]);
62 for(i=0;i<26;i++)
63 {
64 struct node *pre=p->pre;
65 while(!(pre->nxt[i])) pre=pre->pre;
66 if(p->nxt[i])
67 {
68 p->nxt[i]->pre=pre->nxt[i];
69 q[++e]=p->nxt[i];
70 }
71 else
72 p->nxt[i]=pre->nxt[i];
73 }
74 }
75 }
76 int match()
77 {
78 struct node *p=buf;
79 unsigned long long res[4];
80 int len=strlen(str),i,j,ans=0;
81 memset(res,0,sizeof(res));
82 for(i=0;i<len;i++)
83 {
84 p=p->nxt[str[i]-'A'];
85 for(j=0;j<4;j++)
86 res[j]|=(p->bit[j]);
87 }
88 strrev(str);
89 p=buf;
90 for(i=0;i<len;i++)
91 {
92 p=p->nxt[str[i]-'A'];
93 for(j=0;j<4;j++)
94 res[j]|=(p->bit[j]);
95 }
96 for(i=0;i<4;i++)
97 while(res[i])
98 {
99 ans+=(res[i]&1);
100 res[i]>>=1;
101 }
102 return ans;
103 }
104 void decompress()
105 {
106 int p=0,len=strlen(tstr),i;
107 for(i=0;i<len;i++)
108 {
109 if(tstr[i]=='[')
110 {
111 int j,num;
112 char ch;
113 for(j=i+1;j<len&&tstr[j]!=']';j++);
114 ch=tstr[j-1];
115 tstr[j-1]='\0';
116 num=atoi(tstr+i+1);
117 i=j;
118 while(num--)
119 str[p++]=ch;
120 }
121 else
122 str[p++]=tstr[i];
123 }
124 str[p]='\0';
125 }
126 int main()
127 {
128 int test;
129 scanf("%d",&test);
130 while(test--)
131 {
132 int n,i;
133 init();
134 scanf("%d",&n);
135 for(i=0;i<n;i++)
136 {
137 char tmp[1005];
138 scanf("%s",tmp);
139 insert(tmp,i);
140 }
141 makepre();
142 scanf("%s",tstr);
143 decompress();
144 printf("%d\n",match());
145 }
146 return 0;
147 }
148
149