一開始一直WA，之后发现这道题不止一组输入，改成多组输入之后就过了。
利用map把每一个字符串映射到它相应的结点上即可了。
| 11909467 | 2014-10-19 11:54:00 | Accepted | 3065 | 234MS | 16912K | 2754 B | G++ | KinderRiven |
#include<queue>
#include<map>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 55555;
const int max_size = 130;
char ss[1111][55];
map<string,int>vis;
struct Trie{
int next[maxn][max_size];
int fail[maxn];
int val[maxn];
int sz;
int root;
int num[maxn];
int index(char e){
return e - 31;
}
void init(){
sz = 0;
root = newnode();
}
int newnode(){
val[sz] = 0; num[sz] = 0;
memset(next[sz],-1,sizeof(next[sz]));
sz ++;
return sz - 1;
}
void insert(char *str){
int L = strlen(str);
int u = root;
for(int i = 0; i < L; i++){
int e = index(str[i]);
if(next[u][e] == -1)
next[u][e] = newnode();
u = next[u][e];
}
val[u] = 1; //有单词
vis[string(str)] = u;
}
void build(){ //建立失配边
fail[root] = root;
queue<int>q;
for(int i = 0; i < max_size; i++){
if(next[root][i] == -1)
next[root][i] = root;
else{
fail[next[root][i]] = root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = 0; i < max_size; i++){
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else{ //这个点是一个单词的结尾
fail[next[now][i]] = next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
void count(char *str){
int now = root;
int L = strlen(str);
for(int i = 0; i < L; i++){
int e = index(str[i]);
now = next[now][e];
int temp = now;
while(temp != root){
if(val[temp]){ //假设这个结点是个单词末尾
num[temp] ++;
//printf("%d\n",temp);
}
temp = fail[temp];
}
}
}
};
Trie ac;
char _str[2222222];
int main(){
int n;
while(scanf("%d",&n) != EOF){
ac.init();
vis.clear();
getchar();
for(int i = 0; i < n ; i ++){
gets(ss[i]);
ac.insert(ss[i]);
}
ac.build();
gets(_str);
ac.count(_str);
for(int i = 0; i < n; i++){
int t = vis[string(ss[i])];
if(ac.num[t]){
printf("%s: %d\n",ss[i],ac.num[t]);
}
}
}
return 0;
}