QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB
[+5]

# 897. 基本子串字典

Statistics

若非空字符串 S,T 满足 T 既是 S 的前缀也是 S 的后缀,且 |T|<|S| ,则称 T|T|S 的border。

有一个字符串 S ,有 q 次询问,每次给定一个 S 的子串,询问这个串的最短border、最长border、border个数。

输入格式

第一行一个字符串 S。 第二行一个整数 q ,接下来 q 行每行两个数 l,r 表示询问 S[lr] 这个子串,从零开始编号。

输出格式

对每个询问输出一行。若没有border,则输出 −1 ,否则输出三个数表示最短border、最长border、border个数。

样例数据

样例 1 输入

abacaba
2
0 6
1 2

样例 1 输出

1 3 2
-1

样例 2 输入

aaaaaa
1
0 5

样例 2 输出

1 5 5

子任务

|S|,q2×105