【bzoj3483/4212】SGU505 Prefixes and suffixes(询问在线版)

2015年7月7日1,1463

Description

GAL发现了N个特殊的字母序列,由小写字母组成。小L认为,对于两个字符串s1,s2,若s1是某个特殊序列的前缀,s2是该特殊序列的后缀,则称s1,s2被这个序列拥有。

现在小L给出M对s1,s2,对于每对字符串,问它们被几个特殊序列拥有。

Input

第1行一个整数N。

接下来N行,每行一个字符串,代表N个特殊序列。

第N+2行一个整数M。

接下来M行每行一对s1,s2用空格隔开。S1,s2是经过加密的。

设上一问的答案为lastans。解密方法是将s1,s2所有字母向后移动lastans个单位,这时你要把小写字母表当作一个环,比如z的下一个字母是a。

Output

对于每次询问操作,输出一个非负整数表示答案。

Sample Input

3
aaaaa
abacabaa
avtobus
6
a a
y yy
yy y
zzzzz zzzz
zazb bzaz
abac a

Sample Output

2
2
1
1
0
1

HINT

设N个特殊序列总长为L1,所有M组询问总长为L2。L1,L2<=2000000.N<=2000,M<=100000

题解

【FJ2015集训】神牛养成计划

听说不怎么卡暴力,就交了个自然溢出,结果一看,别人哈希都是70分

我40分,代码太丑自带常数大

正解出题人给出的是可持久化trie

卓神现场用神做法ac:对于询问俩串长都小于20的,可知这种类型有解的情况只有2000*20*20种,把这些情况预处理答案用map存一下,然后直接查表

其余的暴力

100分