悲惨故事 长文警告 关于广义 SAM 的讨论

学术版

ix35 @ 2021-06-15 15:47:40

关于广义 SAM 的讨论

因一次惨痛的教训来写这篇帖子。

今天参加联测时，有一道广义 SAM 裸题，本来随便打打就应该过了，结果没想到因为这道题的写挂，让我发现这辈子之前写过的所有广义 SAM 都是错的，同时也发现网络上一些犯有同样错误的博客以及可视化网站。

考虑如下两个字符串构成的广义后缀自动机：

iod
od

我们可以根据这两个字符串建出如下图所示的 Trie，后缀自动机，和 Parent 树。

Trie 中结点的数字表示这个点对应的后缀自动机上的结点。

然而，有一种不常被注意的错误如下图所示：

这种错误似乎是有些普遍的，我们打开洛谷模板题的第一篇题解，来自 @辰星凌 的博客：

https://www.luogu.com.cn/blog/ChenXingLing/solution-p6139

这篇题解中提到三种建立广义 SAM 的方法，并正确地指出了第二种的错误（这和上面我们看到的等价），但是他在第三种算法中说直接运行普通 SAM 的 extend 函数即可得到正确答案，这是错误的。

我找到了博主的 AC 代码并测试，发现这份代码建出的后缀自动机果然有我上面所说的问题。

https://www.luogu.com.cn/record/36889179

接下来我找到了网上的一些后缀自动机可视化网站，抽选了百度出来的第一个结果，以及我平常用的一个网站，调查结果如下：

上图截自 https://mivik.gitee.io/sam-visualizer/，是正确的广义 SAM。

上图截自 https://yutong.site/sam/，犯了我上面所说的错误。

此外还有一些 SAM 可视化网站，如 http://wenhao801.com:5000/，这个网站在输入 \texttt{od|iod} 后表现正常，但是在输入 \texttt{iod|od} 后输出了错误的后缀自动机，不过它的错误之处是明显的，不是我要讨论的范围。

下面我们简单讨论一下这个错误。

错误在哪里

错误演示中，多了 5,7 两个结点，按说多了两个没有任何作用的结点并不影响正确性，但问题就出在它们对应的是 Trie 上的两个结点，而这两个结点对应的实际上应该分别是 6,8 两个结点。

为什么有这种错误无法发现？

在部分题目中，这样建立后缀自动机并不会影响答案的正确性，例如洛谷模板题：https://www.luogu.com.cn/problem/P6139。

题目要我们求出 n 个串的本质不同子串的并的大小，正常的方法是求出广义 SAM 后统计所有点与父亲的 len 差并求和。

而如果出现这种错误，由于 5,6 两个点的 len 相同（都是 1），同理 7,8 两个点的 len 相同（都是 2），所以这里加的一个 0 并没有影响答案，看上去就仿佛 Trie 左边的两个点对应了 6,8 一样。

那么这有什么关系呢？

关系很大，它影响了 SAM 的基本结构。

SAM 中一个串只能属于一个结点，同时我们不允许一个点和它的 link 指向结点的 len 相同，而上图的错误打破了这种结构。

更严重的是，它影响了子树与后缀关系的判定，只要遇到需要通过子树操作刻画以某个串为后缀的所有串，上面的方法就出锅了，例如我今天做的那道题。

错误如何产生

这一点在上面提到的博客中阐述的比较清楚（只是似乎作者没有意识到 Trie 树做法也有这个问题）。

正常来说，我们进行单串 SAM 的插入字符时，设之前的终止结点为 las，首先我们会将 las 的一段没有对应字符出边的点的对应字符出边修改为我们新建的点 cur。

单串 SAM 情况下，las 本身必定没有出边，因为它的 maxlen 就是之前字符串的长度，无法进行任何扩展。

但广义 SAM 就不一样了，las 可能已经有对应出边，但这是一个不连续转移（len_q>len_{las}+1，q 是 las 出边指向的点），如果按照单串 SAM 的运行规则，我们新建一个 q 的克隆 clone，令它取代原先指向 q 的部分转移，同时令 q 和 cur 的 link 都指向 clone。

发现了吗？问题就出在最后一句。

注意到此时由于 len_{cur}=len_{las}+1=len_{clone}，而所有 q 的信息都到了 clone 上，所以 clone 才是我们真正需要的点，而 cur 是一个与之等价但没有任何信息的空壳！

但如果按照一般 SAM 的写法，我们会直接返回 cur。

如何解决

解决这个问题是简单的，插入时判定 las 是否有出边，如果有，那么就返回 clone，否则才返回 cur。

当然，这样的解决不够漂亮，因为如最上面图中的 5,7 结点还是存在，只是不会影响我们的算法。

真正合理的解释是我们根本不需要建立 clone，只需要把 q 的部分信息转移到 cur 即可。

by HikariS @ 2021-06-15 16:17:41

每次让last=1的写法是否也是正确的，只要像您那样判断last是否有出边就可以

by Pecuria @ 2021-06-15 16:17:45

节点数是6

by ix35 @ 2021-06-15 16:22:03

@Tamaki_Iroha

pos[i] 表示字典树上点 i 对应的后缀自动机上的点。

by Pecuria @ 2021-06-15 16:23:45

贴一下我的代码吧，基本照着题解写的，对您这组数据我给出的节点数是6（在线做法）。

和您的解决方案是一样的。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
ll c[2000005][27],len[2000005],tot=1,rt=1,ans,n,fa[2000005],lm;
char s[2000005];
ll insert(ll x,ll last){
    if(c[last][x]&&len[last]+1==len[c[last][x]]) return c[last][x];
    ll now=++tot,ad,prt,flag=0;
    len[now]=len[last]+1;
    while(last&&!c[last][x]){
        c[last][x]=now;
        last=fa[last];
    }
    if(!last){
        fa[now]=rt;
    }
    else{
        prt=c[last][x];
        if(len[prt]==len[last]+1) fa[now]=prt;
        else{
            if(len[now]==len[last]+1) flag=1,ad=now;
            else ad=++tot;len[ad]=len[last]+1;
            for(ll i=1;i<=26;i++) c[ad][i]=c[prt][i];
            fa[ad]=fa[prt];fa[prt]=ad;if(!flag) fa[now]=ad;
            while(last&&c[last][x]==prt){
                c[last][x]=ad;
                last=fa[last];
            }
        }
    }
    return now;
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        scanf("%s",s+1);
        lm=strlen(s+1);
        ll last=1;
        for(ll t=1;t<=lm;t++){
            last=insert(s[t]-'a'+1,last);
        }
    }
    for(ll i=1;i<=tot;i++){
        ans+=len[i]-len[fa[i]];
    }
    printf("%lld",ans);
}

by ix35 @ 2021-06-15 16:24:02

代码：

#include<algorithm>
#include<cstdio>
#include<queue>
#include <bits/stdc++.h>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5,M=1e6+3;
int n,t;char ch[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Trie{
    int O,c[M],fa[M],tr[M][26];
    //fa[x]: Trie树上x的父节点
    //c[x]: Trie树上x的颜色
    Trie(){O=1;}//根初始化为1
    inline void insert(char ch[]){
        Re p=1;
        for(Re i=1;ch[i];++i){
            Re a=ch[i]-'a';
            if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
            p=tr[p][a];
        }
    }
}T1;
struct Suffix_Automaton{
    int O,pos[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
    //pos[x]:Trie上的x节点（路径1->x所表示的字符串）在SAM上的对应节点编号
    //link[i]: 后缀链接
    //trans[i]: 状态转移数组
    Suffix_Automaton(){O=1;}//根初始化为1
    inline int insert(Re ch,Re last){//和普通SAM一样
        Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
    inline void dfs(Re x){
        for(Re i=0,to;i<26;++i)if(to=T1.tr[x][i])
            pos[to]=insert(T1.c[to],pos[x]),dfs(to);
    }
    inline void build(){pos[1]=1,dfs(1);}//dfs遍历Trie树构造广义SAM(Tire树上的根1在SAM上的位置为根1)
    inline void sakura(){
        LL ans=0;
        for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
        printf("%lld\n",ans);
    }
}SAM;
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch);
    SAM.build();
    cout << "Edge: " << endl;
    for (int i=1;i<=SAM.O;i++) {
        for (int j=0;j<26;j++) {
            if (SAM.trans[i][j]) {cout << i << "  " << (char)(j+'a') << "  " << SAM.trans[i][j] << endl;}
        }
    }
    cout << "Link: " << endl; 
    for (int i=2;i<=SAM.O;i++) {
        cout << "link[ " << i << " ] = " << SAM.link[i] << endl;
    }
    cout << "Pos: " << endl;
    for (int i=1;i<=T1.O;i++) {
        cout << "pos[ " << i << " ] = " << SAM.pos[i] << endl;
    }
    return 0;
}

by ix35 @ 2021-06-15 16:24:39

@Tamaki_Iroha

那就说明您学的是对的啊

by Pecuria @ 2021-06-15 16:28:39

@ix35 只能说明博主在写离线dfs做法的时候写挂了，但是题解本身是没问题的。

但是离线dfs做法时间复杂度就是错的。

by Pecuria @ 2021-06-15 16:32:41

看了一下题解对离线做法的解释，确实没有说过要写特判。

不过我一直都写的在线所以一直没觉得有什么问题。

by Pecuria @ 2021-06-15 16:34:44

但是题解的离线bfs做法没写特判却过了您的hack数据

by Prean @ 2021-06-15 16:35:56

话说这种广义SAM是不是就能解决基排的bug了啊。。。

上一页 | 下一页