牛客网暑期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;
}
