具体题目见
HDU2222，其实就是一个裸的多串匹配的问题（给出一个主串和N个子串，求出几个子串在主串中出现过）。
我真是太沙茶了……这么水的题目调了N久，找了N位神犇帮我看代码，最终才找出来BUG……
易疵点：
（1）本题的子串是可以相同的，此时Trie的每个结点要设一个mul值，表示该结点对应的字符串在所有子串中重复的次数，另外，
不要为了省空间把mul定义成char型，有可能所有的字符串全相同，因此需要定义成int（事实证明不会爆空间），这是本沙茶被折磨了这么久的主要原因；
（2）Trie采用静态存储，0号结点作为空结点（NULL），因此真正的结点编号从1开始，另外root一般都是1号结点；
（3）注意在建立自动机以及匹配的时候，所有要沿fail上溯的地方，其边界都是0（NULL，注意不是root）或者找到一个有对应子结点的结点。注意到0还没有找到的处理方法：在建立自动机的时候，将T[j]置为root；在匹配的时候，将x置为root；
代码（模板）（那些标了Attention的地方都是易疵的）：
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
using std::string;
#define re(i, n) for (int i=0; i<n; i++)
#define root 1
const int MAXN = 500001, MAXLEN = 1000001, SZ = 26, INF = ~0U >> 2;
struct node {
int mul, ch[SZ], fail; //Attention
} T[MAXN];
int N, Q[MAXN], res;
string s0, A;
char tmp[MAXLEN], tmp0[51];
void ins()
{
int len = s0.length(), x = root, c;
re(i, len) {
c = s0[i] - 97;
if (!T[x].ch[c]) {T[x].ch[c] = ++N; T[N].mul = 0; re(j, SZ) T[N].ch[j] = 0;}
x = T[x].ch[c];
}
T[x].mul++;
}
void mkf()
{
Q[0] = root; T[root].fail = 0;
int i, j, x;
for (int front=0, rear=0; front<=rear; front++) {
i = Q[front];
re(k, SZ) if (j = T[i].ch[k]) {
x = T[i].fail;
while (x && !T[x].ch[k]) x = T[x].fail; //Attention
if (x) T[j].fail = T[x].ch[k]; else T[j].fail = root; //Attention
Q[++rear] = j;
}
}
}
void solve()
{
int len = A.length(), x = root, y, c; res = 0;
re(i, len) {
c = A[i] - 97;
while (x && !T[x].ch[c]) x = T[x].fail; //Attention
if (!x) x = root; else x = T[x].ch[c]; //Attention
y = x;
while (y) {res += T[y].mul; T[y].mul = 0; y = T[y].fail;} //Attention
}
}
int main()
{
int tests, n;
scanf("%d", &tests);
re(testno, tests) {
N = 1; T[root].mul = 0; re(i, SZ) T[root].ch[i] = 0;
scanf("%d", &n); getchar();
re(i, n) {
gets(tmp0);
s0 = tmp0;
ins();
}
gets(tmp);
A = tmp;
mkf();
solve();
printf("%d\n", res);
}
return 0;
}
【2011年10月19日】今天发现了匹配过程中的一个可优化的地方：对于一个点x以及它的所有返回结点（这里把所有沿着x的失败指针不断上溯直到root路径上的结点都称为返回结点），由于不可重复计数，可以将它们的mul值置为原来mul值的相反数（-mul），而不是0，表示该结点已经统计过。这样在下一次y的上溯过程中一旦发现一个mul值为负的点就不用继续上溯了，因为上面的点一定也已经统计过了。
当然，这仅限于单主串，如果是多主串则需要在每次匹配之前把Trie树中所有结点的mul值（如果是负数的的话）全部重新取反。为了节省时间，可以在匹配过程中把所有统计过的（mul值改为负数的）结点全部放进一个辅助的队列里，然后取反时只要处理队列中的结点就行了。
加入该优化后的代码（solve部分）：
void solve()
{
int len = A.length(), x = root, y, c; res = 0;
re(i, len) {
c = A[i] - 97;
while (x && !T[x].ch[c]) x = T[x].fail;
if (!x) x = root; else x = T[x].ch[c];
y = x;
while (y && T[y].mul >= 0) {res += T[y].mul; T[y].mul = -T[y].mul; y = T[y].fail;}
}
}
下面是优化的实测结果（第一个为优化后的，第二个为优化前的），可以看出，该优化的力度很大。
