#P4212. 神牛的养成计划

    ID: 3427 传统题 1000ms 512MiB 尝试: 404 已通过: 96 难度: 6 上传者: 标签>难度分类普及+/提高-排序与序列处理二分查找二维前缀和归并排序CF1900

神牛的养成计划

神牛的养成计划

题目描述

hzwer 培育出的神牛细胞发生了基因突变。他掌握了 NN 个细胞的 DNA 序列,每个序列都是由小写字母组成的字符串。

一个优秀基因由两个字符串 s1,s2s_1,s_2 描述。如果某个细胞的 DNA 序列以 s1s_1 开头、以 s2s_2 结尾,就认为这个细胞拥有该优秀基因。前缀和后缀可以重叠。给定 MM 次询问,每次求有多少个细胞拥有指定的优秀基因。

输入格式

第一行一个整数 NN。接下来 NN 行,每行一个 DNA 序列,序列总长度为 L1L_1。

随后一行一个整数 MM。接下来 MM 行,每行两个由空格隔开的字符串 s1′,s2′s'_1,s'_2。

设 ansans 为上一个询问的答案。将 s1′,s2′s'_1,s'_2 的每个字母沿字母表向后循环移动 ansans 位,得到实际询问的 s1,s2s_1,s_2。例如 ans=2ans=2 时,qz 移动后得到 sb。首次询问前 ans=0ans=0。

输出格式

每次询问输出一行一个整数,表示拥有该优秀基因的细胞数。

样例 #1

样例输入 #1

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

样例输出 #1

4
7
3
5
5
1
3
5
10
4

数据规模与约定

N≤2×103N\le2\times10^3,M≤105M\le10^5,L1≤2×106L_1\le2\times10^6,所有询问中两个字符串的总长度 L2≤2×106L_2\le2\times10^6。输入字符串只含小写英文字母。