大家好，我是 CQ-FZOIer，C2024 级蒟蒻 CJH。

暑假作业太多了，来补一篇题解。

此题 tag：枚举，暴力；哈希，HASH。

洛谷：P3498 [POI2010]KOR-Beads

洛谷博客。

题意

给定一个长度为 $n$ 的序列，问在序列中连续选取长度为 $k(1 \le k \le n)$ 的序列时字串最多（子串都是可以反转的，一个字串的正序和倒序为一个子串）。

分析题目

1. 因为数组没有办法使用 STL map，所以我们还是只有使用哈希算法来预处理出序列的前后缀，这里我们仿照字符串哈希的 BKDR 算法。
2. 在 $1 \sim n$ 中枚举 $k$，求出每一段序列的哈希值后再用 map（就可以不需要哈希了）存储，判断是否这段哈希值是否存在，如果不存在就可以增加不同子串的数量。

注意事项

1. map 每一次用完以后一定要清空！
2. 哈希前缀从前往后处理，哈希后缀从后往前处理。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 200002
using namespace std;
typedef long long LL;//用 LL 替换 long long，简短代码量。
int n,a[MAXN];
LL Hash1[MAXN],Hash2[MAXN],pn[MAXN];//分别为：前缀哈希、后缀哈希、p 的 n 次幂。
map<LL,bool> M;//判断是否有重合的 Hash1&Hash2。
const int p=103;//选取一个远离 2 的整数次幂的质数。
int kkk[MAXN],size=0;//所有的 k 和能获得最大值的k的个数。
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	pn[0]=1;//这一句很重要！初始化 p^0=1。
	for(int i=1;i<=n;i++)
		Hash1[i]=Hash1[i-1]*p+a[i],pn[i]=pn[i-1]*p;//预处理哈希前缀和 p 的 n 次幂。
	for(int i=n;i;i--)
		Hash2[i]=Hash2[i+1]*p+a[i];//预处理哈希后缀。
	int ans=0;//能获得的最大不同的子串个数。
	for(int k=1;k<=n;k++){
		int s=0;M.clear();//当前长度为 k 能获得的不同的子串个数。
		for(int i=1;i<=n-k+1;i+=k){
			LL hs1=Hash1[i+k-1]-Hash1[i-1]*pn[k],hs2=Hash2[i]-Hash2[i+k]*pn[k];//求区间哈希前缀 & 后缀。
			hs1*=hs2;//两数相乘进行计算。
			if(M[hs1]) continue;//如果已经存在就判断下一个字串。
			M[hs1]=1,s++;//标记此子串已存在，个数增加。
		}
		if(s>ans)
			ans=s,kkk[size=1]=k;//更新答案，个数赋值为 1 后存储当前的 k。
		else if(s==ans)
			kkk[++size]=k;//相等则累加
	}
	printf("%d %d\n",ans,size);
	for(int i=1;i<=size;i++)
		printf("%d ",kkk[i]);//输出所有 k。
	return 0;
}

谢谢大家！