题意：给出两个集合S和T，集合中每个元素是个字符串，而T集合中任一元素都是个子弹，可以打S中的任一怪物，如果子弹是怪物的子串，那么才有伤害值1，若在怪物中出现多次，次数为该子弹打到该怪物的伤害值。每个子弹可以射不同怪物分别一次。求用完所有子弹，每个怪物受到的伤害值。
思路：先将所有子弹插到Trie树中。穷举每个怪物，将其所有的子串在Trie树中找，统计出现的次数，并输出。
（1）插子弹时在结点中记录以该结点为结束的有多少个子弹。
（2）每个怪物只需要截取size个str[i...end]在树中查找。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=; int n, m;
string str[N];
char s[N]; struct node
{
int num; //以本节点结尾的单词个数
node *child[]; //孩子
} pos[N*];
node *tree_gen; int node_cnt;
node * create_node()
{
pos[node_cnt].num=;
for(int i=; i<; i++) pos[node_cnt].child[i]=;
return &pos[node_cnt++];
} void insert_tree(char *p)
{
node *node_p=tree_gen; //指向树根 while(*p!='\0')
{
if( node_p->child[*p-'a']== ) //还没有这叉，就要建
{
node *new_node=create_node(); //创建新节点
node_p->child[*p-'a']=new_node; //连接
node_p=new_node;
}
else //已有这叉，继续往下
node_p=node_p->child[*p-'a']; if( *(p+)=='\0' ) node_p->num++; //以此单词为结尾的
p++;
}
} int check(string t)
{
int ans=;
node *node_p=tree_gen; //指向树根
int r=;
while( node_p!= && r<t.size() )
{
if(node_p->child[ t[r]-'a' ])
node_p=node_p->child[ t[r]-'a' ];
else break;
r++;
ans+=node_p->num;
}
return ans;
} int cal(string &t)
{
int ans=;
for(int i=; i<t.size(); i++)
{
ans+=check(t.substr(i));
}
return ans;
} int main()
{
//freopen("input.txt", "r", stdin);
int t;
cin>>t;
while(t--)
{
scanf("%d%d", &n, &m);
node_cnt=;
tree_gen=create_node(); for(int i=; i<n; i++)
{
cin>>str[i];
}
for(int i=; i<m; i++)
{
scanf("%s",s);
insert_tree(s);
}
for(int i=; i<n; i++)
{
printf("%d\n", cal(str[i]));
}
}
return ;
}
AC代码