优加优智OJ系统
主页
问题
问题分类
模拟竞赛
登录
注册
1353: A Horrible Poem
内存限制:256 MB
时间限制:3.000 S
标准输入输出
题目类型:传统
评测方式:文本比较
上传者:
提交:9
通过:2
提交
提交记录
统计
题目描述
给出一个由小写英文字母组成的字符串
S
,再给出
q
个询问,要求回答
S
某个子串的最短循环节。
如果字符串
B
是字符串
A
的循环节,那么
A
可以由
B
重复若干次得到。
输入格式
第一行一个正整数
n
,表示
S
的长度。
第二行
n
个小写英文字母,表示字符串
S
。
第三行一个正整数
q
,表示询问个数。
下面
q
行每行两个正整数
a,b
,表示询问字符串
S[a..b]
的最短循环节长度。
输出格式
依次输出
q
行正整数,第
i
行的正整数对应第
i
个询问的答案。
输入样例
复制
8 aaabcabc 3 1 3 3 8 4 8
输出样例
复制
1 3 5
数据范围与提示
1 ≤ a
≤
b
≤
n
≤
5x10
5
,
q
≤
2x10
6
分类标签
哈希
提交
提交记录
统计