dwjshift's Blog

用SAM建广义后缀树

| Comments

这篇文已经坑了几个月了,前几天whx问我SAM的时候才想起来……
其实标题这么写也不太对,因为SAM和后缀树本来就是一个东西。不过为了方便区分还是先这么写吧。

Trie上SAM

定义Trie的后缀为从某个节点到根的路径经过的边上的字符依次组成的字符串。注意是从底下到根而不是从根到底下。
考虑构造一个后缀自动机,目标是能识别Trie上的所有后缀。

离线做法

从T的根节点开始bfs,依次将遍历到的节点插入到SAM中。插入的后缀的长度是单调非降的,且后缀不会重复,因此构造狭义后缀自动机的做法依然是适用的。直接在父节点代表的后缀的基础上插入即可。时间复杂度为,其中表示字符集。

在线做法

或者说是dfs做法。这样做无法保证新插入的后缀长度不小于原来的,因此会导致一种情况,就是新节点要成为某个原来的节点的父亲。做法和构造狭义后缀自动机中分叉的情况类似。设为T中叶节点的深度和,则时间复杂度为,具体证明见今年lyy的国家队论文。

Trie上SAM的空间复杂度为O(|T||A|+g(T))。

空间复杂度是,之前一直写错了T_T

广义后缀树

事实上,Trie上SAM就相当于广义后缀树,它包含了所有从叶节点到根的路径构成的字符串。而Trie充当了去除重复后缀的作用。
如果给出一堆字符串要求建出广义后缀树,我们没有必要先把Trie建出来再建Trie上SAM,直接套用它的做法就好了。唯一不同的是,要判断一下新插入的节点是否已经在SAM中出现过。
使用离线做法的话,要按照长度从小到大依次插入后缀。

code(离线做法)

node *addchar(node *u,int c)
{
    if (u->trf[c] && u->trf[c]->len==u->len+1)
        return u->trf[c]; //如果是建Trie上SAM可以去掉这两行
    node *x=++tp,*v;
    x->len=u->len+1;
    for (; u && !u->trf[c]; u->trf[c]=x,u=u->fa);
    if (!u)
        x->fa=root;
    else
        if ((v=u->trf[c])->len==u->len+1)
            x->fa=v;
        else
        {
            *++tp=*v,tp->len=u->len+1,x->fa=v->fa=tp;
            for (; u && u->trf[c]==v; u->trf[c]=tp,u=u->fa);
        }
    return x;
}

code(在线做法)

node *addchar(node *u,int c)
{
    if (u->trf[c] && u->trf[c]->len==u->len+1)
        return u->trf[c]; //如果是建Trie上SAM可以去掉这两行
    node *x=++tp,*v;
    if (u->trf[c])
    {
        *x=*(v=u->trf[c]),x->len=u->len+1,v->fa=x;
        for (; u && u->trf[c]==v; u->trf[c]=x,u=u->fa);
        return x;
    }
    x->len=u->len+1;
    for (; u && !u->trf[c]; u->trf[c]=x,u=u->fa);
    if (!u)
        x->fa=root;
    else
        if ((v=u->trf[c])->len==u->len+1)
            x->fa=v;
        else
        {
            *++tp=*v,tp->len=u->len+1,x->fa=v->fa=tp;
            for (; u && u->trf[c]==v; u->trf[c]=tp,u=u->fa);
        }
    return x;
}

应用

可以做fsf的10K题

在字符集比较小的时候可以替代传统的构建广义后缀树的方法,而且还多了trans边能用。
Q:字符集很大的时候怎么办?
A:直接给出题人寄刀片咯。

可以造一道这样的题:
1、插入某个字符串。
2、在某个字符串前面加一个字符。
3、询问某些信息。
强制在线。
懒癌晚期,哪天心情好再搞吧(大雾

Comments

comments powered by Disqus