本文共 2619 字，大约阅读时间需要 8 分钟。

$$OKR-AHorriblePoem$$

题目链接：

题目大意

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

如果字符串$B$是字符串$A$的循环节，那么$A$可以由$B$ 重复若干次得到。

输入

第一行一个正整数$n(n\le 500000)$，表示$S$的长度。

输出

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

样例输入

8aaabcabc31 33 84 8

样例输出

135

思路

这道题用$hash$来做。

既然知道了怎么判断两个字符串是否相同，就要判断某个小字符串是否是某个字符串的循环节。当然，我们不能直接一个一个地枚举那个字符串里面的小字符串（因为会超时），那怎么办呢？

在枚举循环节的长度的时候，我们不一定要枚举全部的长度，我们只要在循环节循环次数是字符串的长度的约数的情况下才需要枚举这个长度。

代码

#include
   
    #define rr register#define min(x, y) (x) < (y) ? (x) : (y) using namespace std;int n, m, x, y, p = 131, P[500001], hash[500001], b[500001][27], ans;char a[500001];int geth(int l, int r) {   //得到字符串的hash值	return hash[r] - hash[l - 1] * P[r - l + 1];}void find (int length) {   //如果是判断出是循环节的话就判断是否比当前最优解还要优	if (geth(x + length, y) == geth(x, y - length)) ans = min(ans, length);}int gcd(int l, int r) {   //求gcd	if (r == 0) return l;	return gcd(r, l % r);}int read() {   //快读	int an = 0;	char c = getchar();	while (c > '9' || c < '0') c = getchar();	while (c <= '9' && c >= '0') {   		an = an * 10 + c - 48;		c = getchar();	}	return an;}int main() {   	n = read();//读入	scanf("%s", a + 1);//读入		P[0] = 1;//初始化	for (rr int i = 1; i <= n; i++)		P[i] = P[i - 1] * p;//预处理hash的进制	for (rr int i = 1; i <= n; i++)		hash[i] = hash[i - 1] * p + a[i] - 'a' + 1; //转换hash并记录前缀和		for (rr int i = 1; i <= n; i++) {   		for (int j = 1; j <= 26; j++)			b[i][j] = b[i - 1][j];//前缀和出单词出现的位置与频率		b[i][a[i] - 'a' + 1]++;//记录单词的出现	}		scanf("%d", &m);//读入	for (rr int i = 1; i <= m; i++) {   		x = read();//读入		y = read();//读入				int len = y - x + 1;//求出长度		ans = 2147483647;//初始化				for (int i = 1; i <= 26; i++)			len = gcd(len, b[y][i] - b[x - 1][i]);//对小序列中每个字母出现次数取gcd				for (int i = 1; i * i <= len; i++) {   //枚举循环次数			if (len % i) continue;//循环次数须为序列长度的约数			find((y - x + 1) / i);//计算循环次数为i次的结果，更新答案			find((y - x + 1) / (len / i));//计算循环次数为len/i次的结果，更新答案		}				printf("%d\n", ans);//输出	}		return 0;}