给定n个字符串Ai
给定m个字符串Bi
问所有的Bi在每个Ai中出现了多少次
很显然，对Bi建Trie图，然后每次用Ai去匹配的时候，不断查找当前匹配串的最长后缀，这样就能找到答案了
比赛的时候也这样水过了。（又一次我认为这样不会过，但是交上去却过了）
如有有这样的数据的话
1
1 1
10^5个a
10^5个a
那么时间复杂度是10^10,
其实上面不断查找当前匹配串的最长后缀是没必要的，是重复操作的。
如果我们知道当前匹配串的最长后缀包含了多少个Bi，那么就不用去不断回溯了。
所以我们只要在构建fail指针的时候，处理处当前fail指针指向的字符串包含了多少个Bi，那么就不用不断的回溯了。
（哈哈，学到东西了）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/* */
const int N = + ;
struct Node
{
int fail, next[];
int cnt;
void init()
{
fail = -;
cnt = ;
for (int i = ; i < ; ++i)
next[i] = -;
}
}Trie[N];
int size;
void insert(int root, char *str)
{
int idx, cur = root;
for (int i = ; str[i]; ++i)
{
idx = str[i] - 'a';
if (Trie[cur].next[idx] == -)
{
Trie[size].init();
Trie[cur].next[idx] = size++;
}
cur = Trie[cur].next[idx];
}
Trie[cur].cnt++;
}
void makeFail(int root)
{
queue<int> q;
for (int i = ; i < ; ++i)
{
if (Trie[root].next[i] == -)
Trie[root].next[i] = root;
else
{
Trie[Trie[root].next[i]].fail = root;
q.push(Trie[root].next[i]);
}
}
while (!q.empty())
{
int cur = q.front();
q.pop();
for (int i = ; i < ; ++i)
{
if (Trie[cur].next[i] == -)
{
Trie[cur].next[i] = Trie[Trie[cur].fail].next[i];
}
else
{
Trie[Trie[cur].next[i]].fail = Trie[Trie[cur].fail].next[i];
//处理处，当前fail指针指向的字符串包含了多少个Bi
Trie[Trie[cur].next[i]].cnt += Trie[Trie[Trie[cur].fail].next[i]].cnt;
q.push(Trie[cur].next[i]);
} }
}
}
int match(int root, char *str)
{
int i = ;
int idx;
int cur = root;
int ret = ;
while (str[i])
{
idx = str[i] - 'a';
cur = Trie[cur].next[idx];
//int tmp = cur;
//while (tmp != root)
//{
// ret += Trie[tmp].cnt;
// tmp = Trie[tmp].fail;
//} ret += Trie[cur].cnt;
i++;
}
return ret;
}
/*
题目问所有的Bi在每一个Ai中出现的次数 一个串的所有子串可以表示为它所有前缀的后缀
对所有的Bi建trie图
我们可以让每个Ai匹配的时候，就让这个当前字符串不断的去寻找最长后缀，
时间复杂度吵了
，然而数据水，居然过了
*/ char str[];
char str2[];
int main()
{
int t, n, m;
//freopen("d:/in.txt", "r", stdin);
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
int idx = ;
size = ;
Trie[].init();
Trie[].fail = ;
for (int i = ; i < n; ++i)
{
scanf("%s", str + idx);
idx += strlen(str + idx) + ;
}
for (int i = ; i < m; ++i)
{
scanf("%s", str2);
insert(,str2);
}
makeFail();
idx = ;
for (int i = ; i < n; ++i)
{
printf("%d\n", match(, str + idx));
idx += strlen(str + idx) + ;
}
}
return ;
}