String query

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)

Problem Description

有N个字符串,它们的总长度之和<=10W,有M个查询,每个查询是S,[L1,R1] [ L2,R2]的形式,意思是给出字符串S,问S的所有子串中,有多少个子串在给出的第L1到第R1个串中,而且其长度是介于[L2,R2]之间的。

比如对于N = 4

a

aa

aaa

aaaa

给出 aaaaa 1 4 2 3,aaaaa的所有子串是5个"a",4个"aa",3个"aaa",2个“aaaa",1个"aaaaa",出现在第1-4的,且长度介于2 3中的给定串是"aa", "aaa",所以结果为4 + 3 = 7

Input

多组数据,每组数据:

第一行两个正整数N,M(代表有N个字符串,M个查询)

接下来N行,每行一个字符串,均有小写英文字母组成(对于单组数据,所有字符串长度和<=10^5)

接下来有M个查询,每个查询:

第一行一个字符串S(对于单组数据,查询串总长度<=10^6)

第二行4个自然数L1,R1,L2,R2(1 <= L1 <= R1 <= N, 0 <= L2 <= R2 <= 10 ^ 9)

Output

对于每个查询输出一行,符合条件的子串个数

Sample Input

4 1

a

aa

aaa

aaaa

aaaaa

1 4 2 3

Sample Output

7

Source

sweetzero

Manager

Information
Solved Number26
Submit Number93
Problem Tags
data structures
string suffix structures
strings
trees
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel