#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int maxn = 500009;

const ull P = 1000173169;

char S[maxn];

int check[maxn], prime[maxn], N = 0, n;

ull H[maxn], K[maxn];

void init() {

	memset(check, 0, sizeof check);

	for(int i = 2; i <= n; i++) {

		if(!check[i])

			check[i] = prime[N++] = i;

		for(int j = 0; j < N && i * prime[j] <= n; j++) {

			check[i * prime[j]] = prime[j];

			if(i % prime[j] == 0) break;

		}

	}

	H[n] = 0; K[0] = 1;

	for(int i = n - 1; ~i; i--)

	    H[i] = H[i + 1] * P + S[i];

	for(int i = 1; i <= n; i++)

	    K[i] = K[i - 1] * P;

}

inline bool jud(int a, int b, int L) {

	return H[a] - H[a + L] * K[L] == H[b] - H[b + L] * K[L];

}

void Read() {

	cin >> n;

	char* t = S;

	for(; !islower(*t); *t = getchar());

	for(int i = 1; i < n; i++)

	    *++t = getchar();

}

int main() {

	Read();

	init();

	int q; scanf("%d", &q);

	while(q--) {

		int l, r; scanf("%d%d", &l, &r); l--; r--;

		int ans = r - l + 1, t = ans;

		while(t > 1) {

			int x = check[t];

			while(ans % x == 0 && jud(l, l + ans / x, r - l  + 1 - ans / x)) ans /= x;

			for(; t % x == 0; t /= x);

		}

		printf("%d\n", ans);

	}

	return 0;

}

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

第一行一个正整数n (n<=500,000)，表示S的长度。
第二行n个小写英文字母，表示字符串S。
第三行一个正整数q (q<=2,000,000)，表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n)，表示询问字符串S[a..b]的最短循环节长度。

依次输出q行正整数，第i行的正整数对应第i个询问的答案。

8
aaabcabc
3
1 3
3 8
4 8

1
3
5

 

鸣谢 jiangzoi&oimaster