[BJWC2018] Border 的四种求法
题目背景
Scape 一到机房,所有做题的人便都看着他笑,有的叫道,“Scape,你一定又被标准分倍杀了!”他不回答,对柜里说,“测两个程序,看一眼成绩单。”便拷出两个程序。他们又故意的高声嚷道,“你怎么欧拉回路和逆序对都WA了!”……
题目描述
Scape 知道,以上的故事只是 OI 生涯里的一个意外,为了证明自己,他决定教你 $\text{Border}$ 的四种求法。
给一个小写字母字符串 $S$,$q$ 次询问每次给出 $l,r$ ,求 $s_{l\ldots r}$ 的 $\text{Border}$。
$\text{Border}$:对于给定的串 $s$,最大的 $i$ 使得 $s_{1\ldots i} = s_{|s|-i+1\ldots |s|}$。$|s|$ 为 $s$ 的长度。
输入输出格式
输入格式
第一行一个字符串 $S$。
第二行一个整数 $q$ 表示询问个数。
接下来的 $q$ 行每行两个整数 $l,r$ 表示一个询问。
输出格式
对于每组询问输出答案。
输入输出样例
输入样例 #1
abbabbaa
3
1 8
1 7
2 7
输出样例 #1
1
4
3
说明
对于 $30%$ 的数据, $n,q\leq 1000$ 。
对于 $50%$ 的数据, $n,q\leq 2\times 10^4$ 。
对于另外 $30\%$ 的数据,答案至少为 $r-l+1$ 的一半。
对于 $100\%$ 的数据, $n,q\leq 2\times 10^5$ 。