#P18121. Matching Substrings

Matching Substrings

Matching Substrings

给定字符串 a,ba,b,再给定若干询问串 cc。对每个 cc 的每个非空前缀 c1⋯ckc_1\cdots c_k,统计不同字符串 xx 的数量,使得:

  • xx 是 aa 的连续子串;
  • 拼接串 xc1⋯ckxc_1\cdots c_k 是 bb 的连续子串。

允许 xx 为空串。字符串是否相同只按内容判断,与出现位置无关;相同长度的不同字符串也要分别计数。

输入格式

第一行整数 TT,1≤T≤100001\le T\le10000。

每组依次输入字符串 aa、字符串 bb、整数 qq,再输入 qq 个询问串 cc。所有字符串只含小写英文字母,长度均在 [1,150000][1,150000],1≤q≤1500001\le q\le150000。

在整个输入中,所有 ∣a∣|a| 之和、所有 ∣b∣|b| 之和、所有询问串 ∣c∣|c| 之和,分别都不超过150000。

输出格式

每个询问输出一行 ∣c∣|c| 个整数,第 kk 个是前缀 c1⋯ckc_1\cdots c_k 对应的计数。

样例1

4
ab
cababa
5
a
b
ab
ba
c
aaa
aaaaa
4
a
aa
aaa
aaaa
abc
xyz
4
a
xy
z
abc
banana
anaban
5
a
na
an
ban
n
3
2
3 3
2 2
1
4
4 4
4 4 3
4 4 3 2
0
1 1
1
0 0 0
4
3 2
4 2
4 4 4
3

样例2

1
ab
aaba
1
ab
4 2

样例2中,前缀 a 可对应空串、a、b、ab;完整前缀 ab 只对应空串、a。