建立SAM，求出每一个节点最左边的出现位置（即right集合中的最小元素，在树上dfs即可）
枚举左端点i和右端点j（保证j是最小的满足$s[i,j)$不是$s[0,i)$的子串），维护k表示$s[i,j)$所对应的位置，$i+1$可以通过找到$nex[k]$来实现，$j+1$直接在SAM上走即可，显然j单调不减，利用单调性维护即可
求出每一个i所对应的j后，可以直接用区间修改在线段树上做，但由于i单调不减，因此从上一个赋值的位置到这里暴力即可
View Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2000005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 vector<int>v[N]; 8 int V,las,n,nex[N],len[N],mn[N],ch[N][2],f[N<<2]; 9 char s[N]; 10 void add(int c){ 11 int p=las,np=las=++V; 12 len[np]=len[p]+1; 13 while ((p)&&(!ch[p][c])){ 14 ch[p][c]=np; 15 p=nex[p]; 16 } 17 if (!p)nex[np]=1; 18 else{ 19 int q=ch[p][c]; 20 if (len[q]==len[p]+1)nex[np]=q; 21 else{ 22 int nq=++V; 23 len[nq]=len[p]+1; 24 nex[nq]=nex[q]; 25 nex[q]=nex[np]=nq; 26 memcpy(ch[nq],ch[q],sizeof(ch[q])); 27 while ((p)&&(ch[p][c]==q)){ 28 ch[p][c]=nq; 29 p=nex[p]; 30 } 31 } 32 } 33 } 34 void dfs(int k){ 35 for(int i=0;i<v[k].size();i++){ 36 dfs(v[k][i]); 37 mn[k]=min(mn[k],mn[v[k][i]]); 38 } 39 } 40 void down(int k){ 41 f[L]=min(f[L],f[k]); 42 f[R]=min(f[R],f[k]); 43 } 44 void update(int k,int l,int r,int x,int y,int z){ 45 if ((l>y)||(x>r))return; 46 if ((x<=l)&&(r<=y)){ 47 f[k]=min(f[k],z); 48 return; 49 } 50 update(L,l,mid,x,y,z); 51 update(R,mid+1,r,x,y,z); 52 } 53 void query(int k,int l,int r){ 54 if (l==r){ 55 printf("%d ",max(l-f[k],0)); 56 return; 57 } 58 down(k); 59 query(L,l,mid); 60 query(R,mid+1,r); 61 } 62 int main(){ 63 scanf("%s",s); 64 n=strlen(s); 65 V=las=1; 66 memset(mn,0x3f,sizeof(mn)); 67 for(int i=0;i<n;i++){ 68 add(s[i]-'0'); 69 mn[las]=i; 70 } 71 for(int i=2;i<=V;i++)v[nex[i]].push_back(i); 72 dfs(1); 73 memset(f,0x3f,sizeof(f)); 74 for(int i=0,j=0,k=1;i<n;j=max(j,++i)){ 75 for(;(j<n)&&(mn[ch[k][s[j]-'0']]<i);k=ch[k][s[j++]-'0']); 76 if (i<j)update(1,1,n,i+1,j,i); 77 if ((k>1)&&(j-i-1<=len[nex[k]]))k=nex[k]; 78 } 79 query(1,1,n); 80 }