星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

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

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

咋网上用 $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|)$ ,然而常数不见得就比倍增优秀。

//显然这份代码无法通过此题。放上来仅作为参考。
#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$ 的详细内容。