具體題目見
HDU2222，其實(shí)就是一個(gè)裸的多串匹配的問題（給出一個(gè)主串和N個(gè)子串，求出幾個(gè)子串在主串中出現(xiàn)過）。
我真是太沙茶了……這么水的題目調(diào)了N久，找了N位神犇幫我看代碼，最終才找出來BUG……
易疵點(diǎn)：
（1）本題的子串是可以相同的，此時(shí)Trie的每個(gè)結(jié)點(diǎn)要設(shè)一個(gè)mul值，表示該結(jié)點(diǎn)對(duì)應(yīng)的字符串在所有子串中重復(fù)的次數(shù)，另外，
不要為了省空間把mul定義成char型，有可能所有的字符串全相同，因此需要定義成int（事實(shí)證明不會(huì)爆空間），這是本沙茶被折磨了這么久的主要原因；
（2）Trie采用靜態(tài)存儲(chǔ)，0號(hào)結(jié)點(diǎn)作為空結(jié)點(diǎn)（NULL），因此真正的結(jié)點(diǎn)編號(hào)從1開始，另外root一般都是1號(hào)結(jié)點(diǎn)；
（3）注意在建立自動(dòng)機(jī)以及匹配的時(shí)候，所有要沿fail上溯的地方，其邊界都是0（NULL，注意不是root）或者找到一個(gè)有對(duì)應(yīng)子結(jié)點(diǎn)的結(jié)點(diǎn)。注意到0還沒有找到的處理方法：在建立自動(dòng)機(jī)的時(shí)候，將T[j]置為root；在匹配的時(shí)候，將x置為root；
代碼（模板）（那些標(biāo)了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日】今天發(fā)現(xiàn)了匹配過程中的一個(gè)可優(yōu)化的地方：對(duì)于一個(gè)點(diǎn)x以及它的所有返回結(jié)點(diǎn)（這里把所有沿著x的失敗指針不斷上溯直到root路徑上的結(jié)點(diǎn)都稱為返回結(jié)點(diǎn)），由于不可重復(fù)計(jì)數(shù)，可以將它們的mul值置為原來mul值的相反數(shù)（-mul），而不是0，表示該結(jié)點(diǎn)已經(jīng)統(tǒng)計(jì)過。這樣在下一次y的上溯過程中一旦發(fā)現(xiàn)一個(gè)mul值為負(fù)的點(diǎn)就不用繼續(xù)上溯了，因?yàn)樯厦娴狞c(diǎn)一定也已經(jīng)統(tǒng)計(jì)過了。
當(dāng)然，這僅限于單主串，如果是多主串則需要在每次匹配之前把Trie樹中所有結(jié)點(diǎn)的mul值（如果是負(fù)數(shù)的的話）全部重新取反。為了節(jié)省時(shí)間，可以在匹配過程中把所有統(tǒng)計(jì)過的（mul值改為負(fù)數(shù)的）結(jié)點(diǎn)全部放進(jìn)一個(gè)輔助的隊(duì)列里，然后取反時(shí)只要處理隊(duì)列中的結(jié)點(diǎn)就行了。
加入該優(yōu)化后的代碼（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;}
}
}
下面是優(yōu)化的實(shí)測(cè)結(jié)果（第一個(gè)為優(yōu)化后的，第二個(gè)為優(yōu)化前的），可以看出，該優(yōu)化的力度很大。
評(píng)結(jié)果/ACauto.gif)