前言：

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

题意：

题目传送门

给你一个序列，需要求出数 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;
}

写题解不易，点个赞呗。