题解 P3809 【【模板】后缀排序】
teafrogsf
2019-03-20 20:32:21
咋网上用$SAM$建$SA$的题解这么少啊$\cdots\cdots$这又不是啥理性愉悦的东西。
这是一种$O(n)$构建$SA$的方法。常数未与$DC3,SA-IS$对比，但代码难度小于$DC3,SA-IS$与倍增（如果你更熟练写$SAM$）。当然因实际实现的限制，时间复杂度是$O(n|S|)$的，其中$S$是字符集。
首先我们可以发现，反串的$parent$树就是原串的后缀树。
那么有了后缀树，我们怎么求后缀数组呢？
我们直接按字典序$dfs$后缀树，如果遇到了一个合法后缀$x$，那么结点$x$的$sa(x)$就是它的$dfn$。
至于怎么按字典序有一点细节。
实际上，你需要注意后缀树与反串$parent$树虽然形态一模一样，但是你后缀树的一条转移边上的串其实是反串$parent$**树上每个节点代表的串的一部分，而且串的形态是正串的形态而不是反串。因此你不能直接在构造**$SAM$**时求出一个节点的字典，而是需要一些操作。**
具体来说，我们在构建反串$SAM$时记录一下$cur$的$right$**在原串中的位置**，然后我们考虑$link(u)\to u$这条边表示的串实际上是**这个结点表示的最长串的反串去掉**$link(u)$**中已有的部分。**
那我们把上面的位置求出来，每次建后缀树边的时候就可以算出这条边的字典了。
当然本题字符集大小为$62$，因此只能套上一个$map/tree$，时间复杂度退化~~进化~~为$O(n\log|S|)$~~，然而常数不见得就比倍增优秀。~~
```cpp
//显然这份代码无法通过此题。放上来仅作为参考。
#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];
arr link,len,pos,suf;
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;
link[1]=-1;
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]);
for(p=las;p!=-1&&!nex[p][x];p=link[p])nex[p][x]=cur;
if(p==-1)link[cur]=1;
else
{
q=nex[p][x];
if(len[q]==len[p]+1)link[cur]=q;
else
{
clone=++cnt;
len[clone]=len[p]+1,link[clone]=link[q],pos[clone]=pos[q];
memcpy(nex[clone],nex[q],sizeof nex[q]);
for(;p!=-1&&nex[p][x]==q;p=link[p])nex[p][x]=clone;
link[cur]=link[q]=clone;
}
}las=cur;
}
}
void dfs(int u)
{
if(suf[u])++tp,rk[sa[tp]=pos[u]]=tp;
//printf("orz %d %d %d\n",u,link[u],pos[u]);
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);
f(i,2,cnt)G[link[i]][s[pos[i]+len[link[i]]]-'a']=i;
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
欢迎来我的博客找到有关$SAM,SA$的详细内容。