前言：
最近在做哈希的题，发现了这道好题，看题解里很多大佬的方法都很巧妙，自己就发一个较为朴素的方法吧。
题意：
给你一个序列，需要求出数 k，使划分的子串长度为 k 时，不同的子串数量最多。还要注意几件事：
-
子串可以反转，比如 (1,2,3) 看做与 (3,2,1) 相同。
-
如果不能正好划分完，剩下的部分不计算。
-
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;
}
写题解不易，点个赞呗。