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

题意就是一个字符串，复制前n-1个字符后问你有多少种长度n的子串，然后把它们的下标按种类输出来。

1:我们可以找到规律:

(1)对于长度为n的串如果他是一个长度为m的串经过n/m次循环复制而来的,即存在长度为m的循环节。

比如ababab是ab复制三次来的，那么我们这个串首尾相连成环后就存在m种长度为n/m的子串，这个画个图很容易证明。

(2)那么如果没有循环节呢，比如ababca，我们发现他首尾相连成环后一定有n种不同的长度为n的子串。因为成环后，每个长度为n的子串肯定包含一个c，并且每个子串中c的位置都是不同的。

如下:

ababca

babcaa

abcaab

bcaaba

caabab

aababc

那么一定存在n种长度为n的不同子串。

具体做法是利用kmp的next数组。我们知道对于一个长度为n的数组，如果n可以整除next[n]那么他就存在长度为n-next[n]的循环节。求出循环节剩下的就是简单的代码了。

2:我们队当时用后缀数组，具体就是把串前n-1个字符复制一遍，然后跑后缀数组，利用heigh数组的性质，我们可以知道heigt数组求的sa[i]和sa[i-1]的最长公共前缀,那么我们找heigh[i]>=n，然后把sa[i]和sa[i-1]归为一类就行了。

我们开始用nlogn的算法一直在T啊T啊T。神仙队友说nlogn，n才2e6怎么会超时，应该是排序部分超了，然后优化排序，继续T啊T，突然想到有个DC3优化，换DC3后炸内存QAQ，发现数组开多了。有些数组是不需要开三倍的。改一下就过了。

下面给出代码

#include <bits/stdc++.h>
using namespace std;
int nex[1000050];
char s[1000050];
void get_next()
{
    nex[0]=0;
    nex[1]=0;
    int m=strlen(s);
    for(int i=1; i<m; i++)
    {
        int j=nex[i];
        while(j&&s[i]!=s[j]) j=nex[j];
        nex[i+1]=s[i]==s[j]?j+1:0;
    }
}
int main()
{
    scanf("%s",s);
    get_next();
    int n=strlen(s);
    //for(int i=1;i<=n;i++)
    //printf("%d %d\n",i,nex[i]);
    int x=n-nex[n];
    if(n%x!=0)
    {
        printf("%d\n",n);
        for(int i=0; i<n; i++)
            printf("1 %d\n",i);
    }
    else
    {
        printf("%d\n",x);

        for(int i=0; i<x; i++)
        {
            printf("%d",n/x);
            for(int j=i;j<n;j+=x)
            printf(" %d",j);
            printf("\n");
        }
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
const int MAXN = 2e6 + 5;//n*10
int sa[MAXN*3];
int Rank[MAXN];
int Height[MAXN];
int n;
char s[MAXN*3];
int r[MAXN*3];
int wa[MAXN*3],wb[MAXN*3],wv[MAXN*3];
int wws[MAXN*3];

void sort(int *r,int *a,int *b,int n,int m)
{
      int i;
      for(i=0;i<n;i++) wv[i]=r[a[i]];
      for(i=0;i<m;i++) wws[i]=0;
      for(i=0;i<n;i++) wws[wv[i]]++;
      for(i=1;i<m;i++) wws[i]+=wws[i-1];
      for(i=n-1;i>=0;i--) b[--wws[wv[i]]]=a[i];
     return;
}

int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int *r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}

void dc3(int *r,int *sa,int n,int m)
{
    int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
          rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
          else for(i=0;i<tbc;i++) san[rn[i]]=i;
    for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
    for(i=0,j=0,p=0;i<ta && j<tbc;p++)
          sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
    return;
}
int K;
void calHeight(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) Rank[sa[i]] = i;
    for (i = 0; i < n; Height[Rank[i++]] = k)
        for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; ++k);
    return;
}

vector<int> q[MAXN];
bool vis[MAXN];

struct ac{
    int index, id;
}b[MAXN];

int cmp1(ac d, ac f)
{
    return d.id < f.id;
}

inline void solve()
{
    int cnt = 0, f = 0;

    for(int i = 1; i <= n; i++)
    {
        if(Height[i] >= K)
        {
            if(!f)                //如果是一个新种类 
            {
                f = 1;
                cnt++;
                q[cnt].push_back(sa[i - 1]);

                vis[sa[i - 1]] = 1;
            }
            q[cnt].push_back(sa[i]);
            vis[sa[i]] = 1;
        }
        else f = 0;                
    }
    for(int i = 0; i < K; i++)                //统计只一次的 
    {
        if(!vis[i])
        q[++cnt].push_back(i);
    }

    for(int i = 1; i <= cnt; i++) sort(q[i].begin(), q[i].end());

    for(int i = 1; i <= cnt; i++)
    {
        b[i].id = q[i][0];
        b[i].index = i;
    }
    sort(b + 1, b + cnt + 1, cmp1);

    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; i++)
    {
        int index = b[i].index;
        int len = q[index].size();
        printf("%d ", len);
        for(int j = 0; j < len; j++)
        printf("%d%c", q[index][j], j == len - 1 ? '\n' : ' ');
    }

}

int main()
{
    scanf("%s",s);
    int Max=-1;
    n=strlen(s);
    for(int i = 0; i < n - 1; i++) s[i + n] = s[i];
    K = n;
    n += n - 1;
    for(int i=0;i<n;i++){
        r[i]=s[i];
        if(r[i]>Max)Max=r[i];
    }
    r[n]=0;
    dc3(r,sa,n+1,Max+1);
    calHeight(r,sa,n);
    solve();

    return 0;
}