前言：

最近在做哈希的题，发现了这道好题，看题解里很多大佬的方法都很巧妙，自己就发一个较为朴素的方法吧。

题意：

题目传送门

给你一个序列，需要求出数 $k$，使划分的子串长度为 $k$ 时，不同的子串数量最多。还要注意几件事：

1. 子串可以反转，比如 $(1,2,3)$ 看做与 $(3,2,1)$ 相同。

2. 如果不能正好划分完，剩下的部分不计算。

3. $k$ 可能有多个，这时要输出所有的 $k$，顺序任意。

最后输出两行，第一行两个数，表示最多的不同的子串数量和所有可能的 $k$ 的数量。第二行为每一个 $k$。

思路：

这道题肯定要用哈希的（题目标签），因为我们要判断子串是否相同，而如果每一次都去从头到尾匹配，时间复杂度很高，一定会 TLE 飞。但如果用哈希，就可以 $O(1)$ 比较。

不过，考虑子串可以翻转，可以做一个后缀哈希，即从后往前哈希一次，求出的哈希值即为子串反转后的哈希值。

接下来就好写了，用一个 map 来记录某个子串是否出现过，没出现过则记录并统计，最后更新答案即可。

注意每一次循环结束之后 map 要清零（因为存的是这一次的，下一次就用不到了）。

代码：

请勿抄袭。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int base=10000007;
const int N=2e5;
int n,tot,cnt;
int a[N+10];
ull h1[N+10],h2[N+10],power[N+10];
map<ull,bool> mp;
int ans[N+10];
inline void init()
{
	power[0]=1;
	for(int i=1;i<=n;i++) power[i]=power[i-1]*base;
	for(int i=1;i<=n;i++) 
	{
		h1[i]=h1[i-1]*base+a[i];
	}
	for(int i=n;i>=1;i--)
	{
		h2[i]=h2[i+1]*base+a[i];
	}
}
inline ull get_hash(int l,int r,bool f)
{
	if(f==0) return h1[r]-h1[l-1]*power[r-l+1];
	else return h2[l]-h2[r+1]*power[r-l+1];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	init();
	for(int i=1;i<=n;i++)
	{
		if(n/i<tot) break;
		int sum=0;
		for(int j=i;j<=n;j+=i)
		{
			int hash1=get_hash(j-i+1,j,0);
			int hash2=get_hash(j-i+1,j,1);
			if(!mp[hash1]&&!mp[hash2])
			{
				mp[hash1]=1;
				mp[hash2]=1;
				sum++;
			}
		}
		if(sum>tot)
		{
			tot=sum;
			cnt=1;
			ans[cnt]=i;
		}
		else if(sum==tot) ans[++cnt]=i;
		mp.clear();
	}

	printf("%d %d\n",tot,cnt);
	for(int i=1;i<=cnt;i++)
	{
		printf("%d ",ans[i]);
	}
	return 0;
}

写题解不易，点个赞呗。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=2e5+10, P=5154133;
int n, a[N], sta[N], top;
ULL d[N], f[N], g[N];
ULL Hash(int l, int r){return f[r]-f[l-1]*d[r-l+1];}
ULL Hash2(int l, int r){return g[r]-g[l-1]*d[r-l+1];}
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    d[1]=P;for(int i=2;i<=n;i++)d[i]=d[i-1]*P;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*P+a[i];
    for(int i=1;i<=n;i++)g[i]=g[i-1]*P+a[n-i+1];
    int ans=0;top=0;
    map<ULL, bool>v;
    for(int k=1;k*ans<=n;k++)
    {
        int t_ans=0;//t_ans为长度为k时不一样的个数 
		v.clear();
        for(int j=k;j<=n;j+=k)
        {
        	int L=j-k+1, R=j;
            if(t_ans+(n-R+k)/k<ans)break;//剪枝 
            ULL t=Hash(L, R)*d[k]*Hash2(n-R+1, n-L+1);//首位连接判断重复 
            if(v[t]==false)t_ans++;
			v[t]=true;
        }
        if(t_ans>ans){ans=t_ans;top=0;sta[++top]=k;}
        else if(t_ans==ans)sta[++top]=k;
    }
    printf("%d %d\n", ans, top);
    for(int i=1;i<top;i++)printf("%d ", sta[i]);
    printf("%d\n", sta[top]);
    return 0;
}