E-Sort String 字符串hash+hash表做法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+1e5+7, w=26;
const ll INF=2e9;///这个值为1e9可能还会有冲突
void write(int x){
    if(x==0){putchar(48);return;}
    int len=0,dg[20];
    while(x>0){dg[++len]=x%10;x/=10;}
    for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
int len, cnt;
struct has
{
    ll P;
    ll mi_w[maxn];
    ll hs[maxn];
    void init(char *s)
    {
        P=1e9+rand();
        mi_w[0]=1;
        for(int i=1; i<=len; i++)
            mi_w[i]=mi_w[i-1]*w%P;
        for(int i=1; i<=len; i++)
            hs[i]=(hs[i-1]*w+s[i]-'0')%P;
    }
    ll get(int l,int r)
    {
        return ((hs[r]-hs[l-1]*mi_w[r-l+1])%P+P)%P;
    }
    bool ok(int l,int r)
    {
        return (get(1,l)+get(l+1,r)-get(r+1,len))%P==0;
    }
}h[2];
const int Size=2333237;///hash表用的mod
struct Hash{
    int num[Size];
    ll key[Size];
    void init(){
        memset(num, 0, sizeof(num));
        memset(key, -1, sizeof(key));
    }
    int Insert(ll x){
        int num1=x%Size;
        while(key[num1]!=-1){
            if(key[num1]==x){
                return num[num1];
            }
            ++num1;
            if(num1>=Size)
                num1-=Size;
        }
        key[num1]=x;
        num[num1]=cnt++;
        return num[num1];
    }
}th;
char str[maxn];
vector<int> vv[maxn/2];
int main(){
    register int j, i, slen, top, sav;
    register ll aaa;
    srand(time(0));
    scanf("%s", str+1);
    len=slen=strlen(str+1);
    th.init();
    len*=2;
    for(i=1;i<=slen;++i)///翻倍
        str[i+slen]=str[i];
    h[0].init(str);
    h[1].init(str);
    cnt=0;
    for(i=1; i<=slen; ++i){
        aaa=h[0].get(i, i+slen)*INF+h[1].get(i, i+slen);
        sav=th.Insert(aaa);///插入的时候如果插入过这个数字就返回保存的下标值，没插入过就返回新保存的下标值
        vv[sav].push_back(i-1);
    }
    write(cnt);
    putchar('\n');
    for(i=0; i<cnt; ++i){
        sav=vv[i].size();
        write(sav);
        for(j=0; j<sav; ++j)
            putchar(' '), write(vv[i][j]);
        putchar('\n');
    }
}

	

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+7;
int Next[N];
void write(int x){
    if(x==0){putchar(48);return;}
    int len=0,dg[20];
    while(x>0){dg[++len]=x%10;x/=10;}
    for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
void getNext(char *s, int &len){
    Next[0]=-1;
    register int i=0,k=-1;
    while(i<len){
        if(k==-1||s[i]==s[k]){
            Next[++i]=++k;
        }
        else{
            k=Next[k];
        }
    }
}
char str[N];
int main(){
    register int i, j, len, cnt;
    scanf("%s", &str);
    len=strlen(str);
    getNext(str, len);
    if(len%(len-Next[len])==0&&Next[len]){
        cnt=len-Next[len];
        write(len-Next[len]);
        putchar('\n');
        for(i=0; i<cnt; ++i){
            write(len/(len-Next[len]));
            for(j=i; j<len; j+=cnt){
                putchar(' ');
                write(j);
            }
            putchar('\n');
        }
    }else{
        write(len);
        putchar('\n');
        for(i=0; i<len; ++i){
            putchar('1');
            putchar(' ');
            write(i);
            putchar('\n');
        }
    }
}