2619. 询问

单点时限: 2.0 sec

内存限制: 256 MB

Pollux 最近对字符串匹配很感兴趣,他渐渐发现一个有趣的函数,并且他觉得利用这个函数或许可以建立一种新的匹配算法:

对于字符串 S[1…n] 和 i∈[1,n] ,定义 F(i) 为 S 和 S[1…i] 的最长公共后缀的长度。
例如对于串 S[1…11] = zaaxbaacbaa ,则 F(1) = 0 ,F(2) = 1 , F(3) = 2( 注意 S[1…3] = zaa ) ,F(4) = 0 , …… F(10) = 1 ,F(11) = 11 ;

对于串 S[1…n],i∈[1,n] ,S[i…n] 为 S 的后缀;

但是有一点让他犯难的地方就是他不知道如何快速的计算这个函数在 i∈[1,n] 的值,作为 ECNU 的一名编程高手,你能帮助他解决这个问题吗?

输入格式

第一行为一个整数 T, 表示测数数据的组数。
对于每组数据:

第一行为一个字符串 S,只由小写字母组成,如果 len(s) 表示 s 的长度,那么 1 <= len(s) <= 1000000 ;

接下来一个数 N( 1 <= N <= 100000 ),表示询问的次数;

接下来 N 行,每行一个数 x( 1<=x<=len(s))。

输出格式

对于每个 x 输出 F(x);

样例

Input
1
zaaxbaacbaa
11
1
2
3
4
5
6
7
8
9
10
11
Output
0
1
2
0
0
1
3
0
0
1
11

17 人解决,62 人已尝试。

24 份提交通过,共有 260 份提交。

7.3 EMB 奖励。

创建: 15 年前.

修改: 6 年,9 月前.

最后提交: 10 月,2 周前.

来源: 华东师范大学2009校赛

题目标签