#P18121. Matching Substrings
Matching Substrings
Matching Substrings
给定字符串 ,再给定若干询问串 。对每个 的每个非空前缀 ,统计不同字符串 的数量,使得:
- 是 的连续子串;
- 拼接串 是 的连续子串。
允许 为空串。字符串是否相同只按内容判断,与出现位置无关;相同长度的不同字符串也要分别计数。
输入格式
第一行整数 ,。
每组依次输入字符串 、字符串 、整数 ,再输入 个询问串 。所有字符串只含小写英文字母,长度均在 ,。
在整个输入中,所有 之和、所有 之和、所有询问串 之和,分别都不超过150000。
输出格式
每个询问输出一行 个整数,第 个是前缀 对应的计数。
样例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。