区域赛选拔赛-眼睛不需要可以捐给有需要的人

区域赛选拔赛-眼睛不需要可以捐给有需要的人

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在某次培训中,带师兄讲到了\(kmp\)算法,并给出了一道裸题:
给出一个字符串\(S\),有\(Q\)次询问,每次询问给出求\(S[1,r]\)的不等于自身的最长公共前后缀长度。其中\(S[1,r]\)表示\(S\)中第\(1\)个字符到第\(r\)个字符拼接而成的连续子串。
但是有的人就是看错了,看成了求\(S[l,r]\)的不等于自身的最长公共前后缀长度。其中\(S[l,r]\)表示\(S\)中第\(l\)个字符到第\(r\)个字符拼接而成的连续子串。
带师兄笑了:“这样也是可以写的,试试看吧。”
接下来是一些补充定义:如果一个字符串某个前缀与某个后缀相同,那么这个前缀就被称为该字符串的公共前后缀。很明显,任何字符串的最长公共前后缀都是它自己,所以本题中我们将这种情况排除。空串是任何非空字符串的公共前后缀,其长度为\(0\)。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个字符串表示\(S\),\(S\)的长度不超过\(200000\)且仅包含小写英文字母。
第二行一个正整数\(Q(1<=Q<=200000)\),表示询问个数。
接下来\(Q\)行,每行两个用空格隔开的正整数\(l,r(1<=l<=r<=S的长度)\)。

Output

输出\(Q\)行,按照输入顺序,对于每组询问输出一行一个整数,表示对应的不等于自身的最长公共前后缀长度。

Sample 1

Input

aabaaba
3
1 5 
2 7
3 6

Output

2
3
1

Limitation

4s, 1GB for each test case.

Source

wbs

2019区域赛选拔赛再放送

未参加
状态
已结束
规则
ACM/ICPC
题目
11
开始于
2020-08-17 12:00
结束于
2020-08-17 17:00
持续时间
5.0 小时
主持人
参赛人数
9