#P2890. 序列的故事

    ID: 1997 传统题 1000ms 512MiB 尝试: 137 已通过: 72 难度: 6 上传者: 标签>CF2100提高+/省选-周期判定子串哈希双哈希线性筛最小质因子预处理裴蜀等式

序列的故事

题目描述

给出一个由小写英文字母组成的字符串 SS,再给出 qq 个询问,要求回答 SS 某个子串的最短循环节。

循环节的定义:如果字符串 BB 是字符串 AA 的循环节,那么 AA 可以由 BB 重复若干次得到。

输入格式

第一行一个整数 nn 表示 SS 的长度。

第二行 nn 个小写字母表示字符串 SS。

第三行一个整数 qq 表示询问个数。

接下来 qq 行每行两个整数 l,rl,r,表示询问字符串 S[l…r]S[l\dots r] 的最短循环节。

输出格式

共 qq 行,每行一个整数表示答案。

8
aaabcabc
3
1 3
3 8
4 8
1
3
5

数据规模与约定

对于 30%30\% 的数据,1≤q≤1041\leq q\leq 10^4;

对于 42%42\% 的数据,1≤n≤1041\leq n\leq 10^4;

对于 100%100\% 的数据,1≤n≤5×1051\leq n\leq 5\times 10^5,1≤q≤2×1061\leq q\leq 2\times 10^6。