题目描述
给出一个字符串，⻓度为n, q 次询问，每次询问对于这个字符串的一个前缀，最少在后面拼接上多少个字符，使得这个前缀的Border ⻓度大于等于k。
一个字符串s 的Border 定义为，最大的正整数t 使得s ⻓度为t 的前缀和s ⻓度为t 的后缀相等。
输入
第一行一个字符串，只包含小写字⺟。
接下来一个正整数q。
接下来q 行，每行2 个整数l; k，表示询问⻓度为l 的前缀，要使其Border 大于等于k。
n， q <= 2 * 105。
保证数据合法。
输出
q 行，表示每次询问的答案。
样例输入
zhouzhendongakking
4
5 2
6 3
7 2
8 3
样例输出
1
1
2
3
来源/分类