Problem Description
Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.
Input
First line contains T, a number of test cases.
For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m)
1 <= T <= 10
1 <= n <= 100000
1 <= m<= 500000
1 <=|Pi|<=100000
1 <=|Qi|<=100000
∑ni=1|Pi|≤100000
File size is less than 3.5 megabytes.
Output
For each test case, first line contains a line “Case #x:”, x is the number of the case.
For each question, you should print one integer in one line.
Sample Input
1
2 2
aba
ab
a
ab
Sample Output
Case #1:
1
2
Hint
#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int read()
{
char ch = getchar();
while (ch<'0' || ch>'9') ch = getchar();
int x = ch - '0';
while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
return x;
}
int T, n, m, cas = 0;
char s[N];
class SAM
{
const static int maxn = 500005; //节点个数
const static int size = 27; //字符的范围
const static char base = 'a'; //字符的基准
class node
{
public:
node *fa, *next[size];
int len, cnt;
node* clear(int x, int y)
{
fa = 0; len = x; cnt = y;
memset(next, 0, sizeof(next));
return this;
}
}nd[maxn]; //节点的设置
int tot; //总节点数
public:
node *root, *last; //根节点,上一个节点
void clear()
{
last = root = &nd[tot = 0];
nd[0].clear(0, 0);
} //初始化
void insert(char ch, int maxlen)
{
node *p = last, *np = nd[++tot].clear(p->len + 1, maxlen);
last = np;
int x = ch - base;
while (p&&p->next[x] == 0) p->next[x] = np, p = p->fa;
if (p == 0) { np->fa = root; return; }
node* q = p->next[x];
if (p->len + 1 == q->len) { np->fa = q; return; }
node *nq = nd[++tot].clear(p->len + 1, q->cnt);
memcpy(nq->next, q->next, sizeof q->next);
nq->fa = q->fa;
q->fa = np->fa = nq;
while (p &&p->next[x] == q) p->next[x] = nq, p = p->fa;
return;
}
void work()
{
scanf("%s", s);
node * q = root;
for (int i = 0; s[i]; i++)
{
int x = s[i] - base;
if (!q->next[x]) { printf("0\n"); return; }
q = q->next[x];
}
printf("%d\n", min(q->len, q->cnt) - q->fa->len);
}
}sam;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
sam.clear();
rep(i, 1, n)
{
scanf("%s", s);
for (int j = 0; s[j]; j++) sam.insert(s[j], j + 1);
sam.insert('z' + 1, 0);
}
printf("Case #%d:\n", ++cas);
rep(j, 1, m) sam.work();
}
return 0;
}