首页 > 题解 > bzoj 4212 神牛的养成计划

bzoj 4212 神牛的养成计划

Description

Hzwer成功培育出神牛细胞,可最终培育出的生物体却让他大失所望……
后来,他从某同校女神 牛处知道,原来他培育的细胞发生了基因突变,原先决定神牛特征的基因序列都被破坏了,神牛hzwer很生气,但他知道基因突变的低频性,说不定还有以下优秀基因没有突变,那么他就可以用限制性核酸内切酶把它们切出来,然后再构建基因表达载体什么的,后面你懂的……
黄学长现在知道了N个细胞的DNA序列,它们是若干个由小写字母组成的字符串。一个优秀的基因是两个字符串s1和s2,当且仅当s1是某序列的前缀的同时,s2是这个序列的后缀时,hzwer认为这个序列拥有这个优秀基因。
现在黄学长知道了M个优秀基因s1和s2,它们想知道对于给定的优秀基因,有多少个细胞的DNA序列拥有它。

Input

第一行:N,表示序列数
接下来N行,每行一个字符串,代表N个DNA序列,它们的总长为L1
接下来一个M,表示询问数
接下来M行,每行两个字符串s1和s2,由一个空格隔开,hzwer希望你能在线回答询问,所以s1等于“s1”的所有字符按字母表的顺序向后移动ans位(字母表是一个环),ans为上一个询问的答案,s2同理。例如ans=2 “s1”=qz
则s1=sb。对于第一个询问,ans=0
s1和s2的总长度为L2

Output

输出M行,每行一个数,第i行的数表示有多少个序列拥有第i个优秀基因。

Sample Input

10

emikuqihgokuhsywlmqemihhpgijkxdukjfmlqlwrpzgwrwozkmlixyxniutssasrriafu

emikuqihgokuookbqaaoyiorpfdetaeduogebnolonaoehthfaypbeiutssasrriafu

emikuqihgokuorocifwwymkcyqevdtglszfzgycbgnpomvlzppwrigowekufjwiiaxniutssasrriafu

emikuqihgokuorociysgfkzpgnotajcfjctjqgjeeiheqrepbpakmlixyxniutssasrriafu

emikuqihgokuorociysgfrhulymdxsqirjrfbngwszuyibuixyxniutssasrriafu

emikuqihgokuorguowwiozcgjetmyokqdrqxzigohiutssasrriafu

emikuqihgokuorociysgsczejjmlbwhandxqwknutzgdmxtiutssasrriafu

emikuqihgokuorociysgvzfcdxdiwdztolopdnboxfvqzfzxtpecxcbrklvtyxniutssasrriafu

emikuqihgokuorocsbtlyuosppxuzkjafbhsayenxsdmkmlixyxniutssasrriafu

emikuqihgokuorociysgfjvaikktsixmhaasbvnsvmkntgmoygfxypktjxjdkliixyxniutssasrriafu

10

emikuqihgokuorociysg yxniutssasrriafu

aiegqmedckgqknky eqpoowonnewbq

xfbdnjbazhdnhkhvb qrqgbnmlltlkkbtyn

bjfhrnfedlhrlolzfv qppxpoofxcr

zhdfpldcbjf stsidponnvnmmdvap

zhdfpldcbjfpjmjxdt gdstsidponnvnmmdvap

dlhjtphgfnjtnqnbhxr wxwmhtsrrzrqqhzet

bjfhrnfedlhrlolzfv frqppxpoofxcr

zhdfpldcbjf dponnvnmmdvap

ucyakgyxweakehes nondykjiiqihhyqvk

Sample Output

4

7

3

5

5

1

3

5

10

4

HINT

N<=2000

L1<=2000000

M<=100000

L2<=2000000

题解

先把所有的串sort一下,让前缀一样的在一个区间里。

然后把这些串正着插到一个Trie树里。每个节点上记下这个点能到的串的l和r(因为sort了所以一定是在一个区间内)

再把这些串倒着插到一个可持久化Trie树里。这样对于询问在Trie里先找这个区间所对应的lr,然后再在可持久化Trie里面匹配下。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×