# 星星灰暗着。

### 题解 P3809 【【模板】后缀排序】

posted on 2019-03-20 20:32:21 | under 题解 |

//显然这份代码无法通过此题。放上来仅作为参考。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define f(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;i=-(~i))
const int neko=100010,seko=200010;
int n,sa[neko],rk[neko],height[neko];
typedef int arr[seko];
int nex[seko][26],G[seko][26];
char s[neko];
namespace SAM
{
int las=1,cur,cnt=1,tp=0;
void extend(char *s)
{
int x,p,q,clone;
f(i,1,n)
{
x=s[i]-'a',cur=++cnt;
len[cur]=len[las]+1,pos[cur]=n-i+1,suf[cur]=1;
//printf("qwq %d %d %d\n",cur,pos[cur],col[cur]);
else
{
q=nex[p][x];
else
{
clone=++cnt;
memcpy(nex[clone],nex[q],sizeof nex[q]);
}
}las=cur;
}
}
void dfs(int u)
{
if(suf[u])++tp,rk[sa[tp]=pos[u]]=tp;
for(int v:G[u])if(v)dfs(v);
}
}
namespace SA
{
using namespace SAM;
void getsa(char *s)
{
std::reverse(s+1,s+n+1),extend(s),std::reverse(s+1,s+n+1);
dfs(1);
}
void getheight(char *s)
{
int ans=0,x;
f(i,1,n)
{
if(ans)--ans;
x=sa[rk[i]-1];
if(x)
f(j,ans,n-i+1)if(s[x+j]!=s[i+j])
{height[rk[i]]=ans=j;break;}
//printf("%d %d %d\n",x,i,ans);
}
}
}
int main()
{
freopen("SA.in","r",stdin);
freopen("SA.out","w",stdout);
using namespace SA;
scanf("%s",s+1),n=strlen(s+1);
getsa(s),getheight(s);
f(i,1,n)printf("%d%c",sa[i],i^iend?' ':'\n');
f(i,2,n)printf("%d%c",height[i],i^iend?' ':'\n');
return 0;
}


$P.S.$
https://www.luogu.org/blog/teafrogsf/post-LSTAM
https://www.luogu.org/blog/teafrogsf/post-SA