Suffix Automation

Time Limit: 12000/6000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

给你一个字符串集合(包含若干个字符串),最多10w次询问

每次询问 i 串的a后缀跟 j 串的 b 后缀的最长的"特殊"公共前缀,这个公共前缀需要在字符串集合中出现.

比如有如下三个串

a

aaab

abaa

有一个询问

1 2 2 2

表示第一个串的从2位置开始的后缀 跟 第二个串的从2位置开始的后缀比较

然后我们发现有一个公共的前缀a,恰好这个a出现在字符串集合里面,所以答案是1

(两种下标都从0开始)

Input

第一行是T,表示数据的组数

每组的第一行输入一个正整数n
接下来n行输入n个字符串(由小写字母构成),保证n个字符串的总长度不超过50万

接着输入一个正整数m (m <= 100000),表示询问的数量

接下来m行每行输入四个整数i, a, j, b

Output

对于每个询问,输出一个数。如果无解,输出-1

Sample Input

1

3
abcde
abde
d
1
0 3 1 2

Sample Output

Case 1:
1

Source

wuyiqi

Manager

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