今天刚刚把Trie图的模板弄到了，并且解决一个简单的多模匹配的问题HDU2222,想到上次做福州赛区的那道题，今天就套模板做了一下，很快乐地就AC了！ 呵呵……其实也没那么顺利！

     第一次提交超空间了！主要是我傻呼呼的把子串反过来插入Trie图中，后来看书上，原来是把母串反转，然后再查一次就OK了！

      第二次提交果断WA了，后来打印解压的结果才发现，自己忘记了把解压缩的母串末尾加上结束符 s[end]='\0';

      第三次提交果断AC了！不管怎么样，感觉挺爽的 呵呵！

把代码贴上来吧！

1. /* 
2.  * Trie图：解决多串匹配问题 
3.  * hdu2222 
4.  * */ 
5. #include<stdio.h> 
6. #include<string.h> 
7. #include<queue> 
8. using namespace std; 
9. #define M   6000000 
10. char word[1105]; 
11. char ds[M]; 
12. char s[M]; 
13. char rs[M]; 
14. struct Node{ 
15.     int tail; 
16.     Node *prefix; 
17.     Node *next[26]; 
18.     Node(){ 
19.         memset(next,0,sizeof(next)); 
20.         tail=0; 
21.     } 
22. }*root; 
23. void init(){ 
24.     root=new Node(); 
25. } 
26. void insert(char *word){ 
27.     Node *p=root; 
28.     int idx; 
29.     while(*word){ 
30.         idx=*word-'A'; 
31.         if(p->next[idx]==0){ 
32.             p->next[idx]=new Node(); 
33.         } 
34.         p=p->next[idx]; 
35.         word++; 
36.     } 
37.     p->tail++; 
38. } 
39. void add_prefix(){ 
40.      root->prefix = NULL; 
41.     deque<Node* > q; 
42.     q.push_back(root); 
43.  
44.     while(!q.empty()) { 
45.         Node* tmp = q.front(); 
46.         Node* p = NULL; 
47.         q.pop_front(); 
48.         for(int i = 0; i < 26; ++i) { 
49.             if(tmp->next[i] != NULL) { 
50.                 if(tmp == root) tmp->next[i]->prefix = root; 
51.                 else { 
52.                     p = tmp->prefix; 
53.                     while(p != NULL) { 
54.                         if(p->next[i] != NULL) { 
55.                             tmp->next[i]->prefix = p->next[i]; 
56.                             break; 
57.                         } 
58.                         p = p->prefix; 
59.                     } 
60.                     if(p == NULL)   tmp->next[i]->prefix = root; 
61.                 } 
62.                 q.push_back(tmp->next[i]); 
63.             } 
64.         } 
65.     } 
66. } 
67. void reverse(char *s){ 
68.     int len=strlen(s); 
69.     int i,j; 
70.     for(i=len-1,j=0;i>=0;i--){ 
71.         rs[j++]=s[i]; 
72.     } 
73.     rs[j]=0; 
74.     //printf("rs=%s\n",rs); 
75. } 
76. int search(char *st){ 
77.     int cnt = 0, t; 
78.             Node* p = root; 
79.             while(*st) { 
80.                 t = *st - 'A'; 
81.                 while(p->next[t] == NULL && p != root) { 
82.                     p = p->prefix; 
83.                 } 
84.                 p = p->next[t]; 
85.                 if(p == NULL)   p = root; 
86.  
87.                 Node* tmp = p; 
88.                 while(tmp != root && tmp->tail != -1) { 
89.                     cnt += tmp->tail; 
90.                     tmp->tail = -1; 
91.                     tmp = tmp->prefix; 
92.                 } 
93.                 st++; 
94.             } 
95.      return cnt; 
96. } 
97. //把字符串解压缩出来 
98. void decode(){ 
99.     int len_ds=strlen(ds); 
100.     int i,j,k,len; 
101.     i=j=0; 
102.     while(i<len_ds){ 
103.         if(ds[i]>='A'&&ds[i]<='Z'){ 
104.             s[j++]=ds[i]; 
105.         }else if(ds[i]=='['){ 
106.             i++;//把']'跳过 
107.             len=0; 
108.             while(ds[i]>='0'&&ds[i]<='9'){ 
109.                 len=len*10+(ds[i]-'0'); 
110.                 i++; 
111.             }//已经跳到了字母 
112.             for(k=0;k<len;k++){ 
113.                 s[j++]=ds[i]; 
114.             } 
115.             i++;//跳到']'的位置 
116.         } 
117.         i++; 
118.     } 
119.     s[j]=0;//这句一定不能少了！我的一次WA就贡献在这里了 
120. //  printf("decode:%s\n",s); 
121. } 
122. int main(){ 
123.     int t,n,i; 
124.     scanf("%d",&t); 
125.     while(t--){ 
126.         init(); 
127.         scanf("%d",&n); 
128.         for(i=0;i<n;i++){ 
129.             scanf("%s",word); 
130.             insert(word); 
131.         } 
132.         add_prefix(); 
133.         scanf("%s",ds); 
134.         decode();reverse(s); 
135.         printf("%d\n",search(s)+search(rs)); 
136.     } 
137. }