多组数据呀呀呀。然后我们只用去掉那个count1=-1就好了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int n = 26;
int vis[3000];
struct Trie
{
Trie *next[n];
Trie *fail;
int count1;
int v;
Trie()
{
fail=NULL;
for(int i=0;i<n;i++)
next[i]=NULL;
count1=0;
v=0;
}
};
Trie *root;
void buildTrie(char *str,int num)
{
int len=strlen(str);
Trie *p=root;
for(int i=0;i<len;i++)
{
int id=str[i]-'A';
if(p->next[id]==NULL)
p->next[id]=new Trie();
p=p->next[id];
p->v=num;
}
p->count1=num;
}
void buildfail()
{
queue <Trie* > q;
q.push(root);
while(!q.empty())
{
Trie *p=q.front();q.pop();
for(int i=0;i<n;i++)
{
if(p->next[i]!=NULL)
{
if(p==root) p->next[i]->fail=root;
else
{
Trie *temp=p->fail;
while(temp!=NULL)
{
if(temp->next[i]!=NULL)
{
p->next[i]->fail=temp->next[i];
break;
}
temp=temp->fail;
}
if(temp==NULL) p->next[i]->fail=root;
}
q.push(p->next[i]);
}
}
}
}
void qurey(char *str)
{
int len=strlen(str);
Trie *p=root;
len--;
for(int i=0;i<len;i++)
{
if(str[i]>='A'&&str[i]<='Z')
{
int id=str[i]-'A';
while(p->next[id]==NULL&&p!=root)
p=p->fail;
p=p->next[id];
if(p==NULL) p=root;
Trie *temp=p;
int flag=0;
int k=temp->v;
while(temp!=root)
{
vis[temp->count1]++;
temp=temp->fail;
}
}
else p=root;
}
}
char s[1005][100];
char str[2000010];
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
root=new Trie();
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
buildTrie(s[i],i);
}
buildfail();
getchar();
fgets(str,2000010,stdin);
memset(vis,0,sizeof(vis));
qurey(str);
for(int i=1;i<=n;i++)
{
if(vis[i]>0) printf("%s: %d\n",s[i],vis[i]);
}
}
return 0;
}