牛客网暑期ACM多校训练营（第三场）E hash解法

复制一遍字符串，然后预处理hash表。之后for每个起始位置，可以在O(1)的时间获取子串的hash值，然后扔进map分类即可。对于这种写法字典序不需要特殊处理。
这个题卡常…有两个点要注意一下。
1.mod取1e9+7会冲突(过了62.5%的数据)，而且每次%常数很大，会tle，这里选用了ull(自动%2^64)。

#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e6+10;
const ll mod=1e9+7;
/*********************************  head  *********************************/
struct hash_table
{
    ull seed;
    ull Hash[MAX],tmp[MAX];
    void set(ull _seed)
    {
        seed=_seed;
    }
    void work(char *s,int n)
    {
        ll i,j;
        tmp[0]=1;
        Hash[0]=0;
        for(i=1;i<=n;i++) tmp[i]=tmp[i-1]*seed;
        for(i=1;i<=n;i++) Hash[i]=(Hash[i-1]*seed+(s[i]-'a'));
    }
    ull get(int l,int r)
    {
        return (Hash[r]-Hash[l-1]*tmp[r-l+1]);
    }
}h;
char s[MAX];
VI res[MAX];
int main()
{
    int i,j,len,tot;
    while(~scanf("%s",s+1))
    {
        len=strlen(s+1);
        for(i=len+1,j=1;j<=len;i++,j++) s[i]=s[j];
        h.set(23333);
        h.work(s,len*2);
        unordered_map<ull,int> mp;
        tot=0;
        for(i=1;i<=len;i++)
        {
            ull tmp=h.get(i,i+len-1);
            if(!mp.count(tmp)) mp[tmp]=++tot;
            res[mp[tmp]].pb(i-1);
        }
        printf("%d\n",tot);
        for(i=1;i<=tot;i++)
        {
            printf("%d",sz(res[i]));
            for(auto it:res[i]) printf(" %d",it);
            puts("");
            res[i].clear();
        }
    }
    return 0;
}