UOJ#35 后缀排序 SAM做法

大家好我是oscar..这可能是我第一次发博客诶..

由于我比较弱，所以可能讲了一些大家都会的东西...求不D...

好了不说太多，先步入正题...

今天我们的挑战是：不建后缀数组完成任务（网上的做法好像都是建出后缀数组再用后缀数组的性质算出height数组）

假装大家都会后缀自动机啦（我这种蒟蒻花了约一个星期才搞懂）

首先将从last到root用suffix link连接的路径上的节点标上结束标记（

inline void update()
{
    node *p=last;
    while(p!=root)
    {
        p->isend=1;
        p=p->link;
    }
}

由于后缀自动机上所有路径能表示出原串的所有子串，所有以一个有标记节点结束的路径能表示出原串的所有后缀

于是可以从根节点DFS一遍，每次有分岔时优先走字典序比较小的转移，途中遇到有结束标记的节点则输出（原串总长度-DFS到当前节点经过长度+1），这样就完成了第一部分的任务（？）

第二部分的任务是找出排序后相邻两个后缀的最长公共前缀...我们发现在第一部分的DFS中正好排序后位置相邻的后缀访问顺序也是连着的，只需要求相邻两个访问的后缀的“LCA”就可以啦

贴代码走人

~~鬼故事，进度条~~

int lcp[MAXN],minn,cnt;
void dfs(node *u,int len=0)
{
    if(u->isend)
    {
        printf("%d ",totlen-len+1);//totlen为字符串总长
        lcp[++cnt]=minn;            //更新LCP信息
        minn=len;
    }
    for(int x=0;x<sigma;x++)
    {
        if(u->next[x])
        {
            if(len<minn)minn=len;//用来记录LCP长度
            dfs(u->next[x],len+1);
        }
    }
}

呃...等等...为什么我TLE了？

貌似这样搜索会做好多重复工作诶...（应该是 $ O(n^2) $ 的）

我们来想办法优化一下

由于不需要输出路径上的所有字符，所以只需要考虑路径长度

那么只有一种走法的路径就可以被压缩成一条边

也就是说这样的路径↓

$ \Huge \bigcirc ---1--> \bigcirc ---1--> \bigcirc ---1--> \bigcirc $

可以压缩成这样↓

$ \Huge \bigcirc ---3--> \bigcirc $

而不改变~~拓扑结构~~DFS结果

这...就是...传说中的...路径压缩？

typedef pair<node*,int> pni;
pni find(node *u)
{
    if(!u->fast)return make_pair(u,0);
    pni _=find(u->fast);
    u->fast=_.first;
    u->fastlen+=_.second;
    return make_pair(u->fast,u->fastlen);
}

对比一下并查集的路径压缩（大雾）

typedef pair<int,int> pii;
pii find(int x)
{
    if(!pa[x])return make_pair(x,shift[x]);
    pii _=find(pa[x]);
    pa[x]=_.first;
    shift[x]^=_.second;
    return make_pair(pa[x],shift[x]);
}

好像没啥区别（大雾）

还需要预处理一下哪些边可以被压缩掉（动态求好像是错的，我不太明白为什么，可能是我写挂了），

把代码扔进一开始的update函数里

inline void update()
{
    node *p=last;
    while(p!=root)
    {
        p->isend=1;
        p=p->link;
    }
   //更新部分↓
    for(int i=1;i<=top;i++)
    {
        node *t=&pool[i],*q=0;
        if(t->isend)continue;
        int c=0;
        for(int ch=0;ch<sigma;ch++)
        {
            if(t->next[ch])
                ++c,q=t->next[ch];
        }
        if(c==1)
        {
            t->fast=q;
            t->fastlen=1;
        }
    }
   //更新部分↑
}

最后在搜索的时候判一下能不能走被压缩的路径就好啦

int lcp[MAXN],minn,cnt;
void dfs(node *u,int len=0)
{
    if(u->isend)
    {
        printf("%d ",totlen-len+1);
        lcp[++cnt]=minn;
        minn=len;
    }
   //更新部分↓
    if(u->fast)
    {
        find(u);
        dfs(u->fast,len+u->fastlen);
    }
   //更新部分↑
    else
        for(int x=0;x<sigma;x++)
        {
            if(u->next[x])
            {
                if(len<minn)minn=len;
                dfs(u->next[x],len+1);
            }
        }
}

这样复杂度为什么是对的呢？

我数学不好，不会证明，那就来感性理解一下

$ \bullet $ 经过“路径压缩”后的自动机构成一棵树

$ \bullet $ 叶子结点数（=原串后缀数）是 $ O(n) $ 的

$ \bullet $ 非叶子结点数（ $ \leq $ 叶子节点数-1）是 $ O(n) $ 的

$ \bullet $ 树的边数是 $ O(n) $ 的

$ \bullet $ 遍历这棵树是 $ O(n) $ 的

应该是这个意思吧QWQ反正跑得飞快QWQ

于是我就这么通过了 UOJ#35 后缀排序通过记录

第一次写后缀自动机可能写挂了，欢迎dalao来hack

P.S.这种方法貌似在LOJ上会被卡内存...悲剧了...

oscar的博客

博客

评论

发表评论