提示: 欢迎访问OurACM平台。
Problem 2246 AC自动机

Accept: 8    Submit: 92
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

某一天YellowStar学习了AC自动机,可以解决多模式匹配问题。YellowStart当然不会满足于此,它想进行更深入的研究。

YellowStart有一个母串S,以及m个询问串T,它发现如果把母串删除掉一个子串,把剩余的串按原先顺序拼接起来,某些询问串T就可能出现在这个新的母串中。

现在,对于第i个询问串Ti,YellowStar想知道,母串最多可以删除多长的子串,使得该询问串出现在新的母串的子串中。

Input

第一行输入T,表示有T组样例(T <= 20)

每组样例第一行为母串S(1 <= |S| <= 1e5)

接下来一个数字m,表示m次询问

接下来m个询问,每个询问一行询问串T(1 <= |T1| + |T2| + ... + |Tm| <= 1e5)

所有串包含的字母均为小写字母'a'-'z'

Output

每组样例输出m行,表示m次询问的答案,如果答案不存在输出-1

Sample Input

1 zelxaaaasdaje 4 ze lxje zj sb

Sample Output

11 7 10 -1

Hint

对于第一个样例

第一个询问删去elxaaaasdaj这个子串

第二个询问删去aaaasda这个子串

第三个询问删去elxaaaasda这个子串

第四个询问无论删去任何一个子串都不存在答案

long long类型请用%I64d输出

Source

FOJ有奖月赛-2017年4月(校赛热身赛)

Submit  Back  Status  Discuss