#YDRS002B. 比赛也需要懂套路
比赛也需要懂套路
题目背景
众所周知,一场比赛需要有 道套路题,用于考察选手的知识储备。
但实际上,这道题不需要什么知识储备,但还是很套路。一般这种题,我们称之为“好题”。所以欢迎大家来做这道好题 (?) 。
题目描述
定义:若字符串 可以由若干个相同的字符串 依次连接得到,则可以称 是 的一个循环节。
例如 :
abc
是abcabc
的循环节。ABA
不是ABABA
的循环节。ttt
是ttttttttt
的循环节。
显然,有的字符串可以存在多个循环节。例如 aaaaaa
的循环节可以是a
、aa
、aaa
。
现在给你一个字符串 以及 个询问。每个询问会通过区间的形式来指定 的一个子串,请你为这个子串寻找循环节,并输出其中最短那个的长度。
输入格式
第 行共一个正整数 ,表示字符串 的长度。
第 行共一个长度为 且仅有小写英文字母的字符串 。
第 行共一个正整数 ,表示询问个数。
第 行,每行包含两个正整数 ,表示询问子串 的循环节的最短长度。
注意:本题约定字符串的下标由 开始编号。
输出格式
输出共 行,每行一个整数表示答案。
样例 #1
样例输入 #1
8
aaabcabc
4
3 8
4 8
1 3
1 8
样例输出 #1
3
5
1
8
样例输入 #2
72
abababcabababcabababcabababcabababcabababcabababcabababcabababababababab
8
1 6
8 13
15 20
1 21
1 56
8 56
1 55
57 72
样例输出 #2
2
2
2
7
7
7
55
2
提示
对于前 的数据,保证 。
对于前 的数据,保证 。
对于前 的数据,保证 。
对于全部 的数据,保证 ,,。
Related
In following contests: