AC自動機。。建好字典樹，找到fail指針。然後查詢。存模版題，需要注意當查到不是大寫字母的時候要 改變p=root.而且字符串可以重復出現。
[cpp]
#include<cstdio>
#include<cstring>
using namespace std;
char str[2000100];
int head,tail;
struct node{
node *fail;
node *next[26];
int cnt,id;
node(){
cnt=0; fail=NULL; memset(next,NULL,sizeof(next));
} www.2cto.com
} *q[500000];
char s[1010][55];
int cnt[1010];
void insert(node *root,char str[],int id){
node *p=root; int i=0;
while(str[i]){
int index=str[i]-'A';
if(p->next[index]==NULL) p->next[index]=new node();
p=p->next[index]; i++;
}
p->cnt++; p->id=id;
}
void build_ac(node *root){
node *p=NULL;
q[head++]=root;
while(head!=tail){
node *temp = q[tail++];
for(int i=0;i<26;i++){
if(temp->next[i]!=NULL){
if(temp==root) temp->next[i]->fail=root;
else{
p=temp->fail;
while(p!=NULL){
if(p->next[i]!=NULL){
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
void query(node *root){
int i=0; node *p=root; int index;
while(str[i]){
if(str[i]>='A'&&str[i]<='Z'){
index=str[i]-'A';
while(p->next[index]==NULL&&p!=root) p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root&&temp->cnt>0){
cnt[ temp->id ]++;
temp=temp->fail;
}
}
else
p=root;
i++;
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(cnt,0,sizeof(cnt));
node *root=new node();
head=tail=0;
for(int i=0;i<n;i++) scanf("%s",&s[i]),insert(root,s[i],i+1);
build_ac(root);
scanf("%s",str);
query(root);
for(int i=1;i<=n;i++){
if(cnt[i]>0){
printf("%s: %d\n",s[i-1],cnt[i]);
}
}
}
return 0;
}
