广义后缀自动机

广义 SAM。这玩意和 SAM 的关系就类似 AC 自动机和 kmp 的关系，也就是可以处理多个串之间的问题。就像 AC 自动机是 kmp 在 trie 上的拓展，广义 SAM 也是 SAM 在 trie 上的拓展。

首先你必须保证你完全理解了 SAM 是个什么东西。要不然以下的东西大概一定会看不懂。

oiwiki 上提到两种常见的假写法：

1. 把每个串连起来，中间加分隔符，建 SAM ，然后通过某些奇技淫巧手段（比如根据分隔符判断）处理。
2. 每次插入一个串前，last 指针清空，然后插入。

显然第一种大多数情况下没什么意义。第二种据说可以卡。下面来讲正确的方法。

离线构建

离线构建，就是先把 trie 建出来然后在 trie 的基础上建立广义 SAM。

SAM 的构建可以看作不断插入 \(\text{len}\) 严格递增的值，且差值为 \(1\)。所以我们可以把 trie 进行拓扑排序，按照这个顺序插入 SAM，得到广义 SAM。

区别在于，普通的 SAM 的 last 就是上一个节点，但是广义 SAM 不太一样，是字典树上的父亲。因此我们只需要在普通 SAM 的基础上加一个拓扑排序，再加一个数组保存 trie 上的每个节点对应 SAM 的哪个节点，就可以建立广义 SAM，复杂度显然为线性。

洛谷板子：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char s[1000010];
int n;
long long ans;
struct Trie{
    int cnt,trie[1000010][26],fa[1000010],col[1000010];
    Trie(){cnt=1;}
    void ins(char s[]){
        int p=1,len=strlen(s+1);
        for(int i=1;i<=len;i++){
            if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++cnt,col[cnt]=s[i]-'a',fa[cnt]=p;
            p=trie[p][s[i]-'a'];
        }
    }
}T;
struct Sam{
    int cnt,pos[2000010],fa[2000010],len[2000010],trie[2000010][26];
    //pos是trie上的每个节点对应SAM的哪个节点
    Sam(){cnt=1;}
    int ins(int ch,int last){
        int p=last;last=++cnt;
        len[last]=len[p]+1;
        while(p&&!trie[p][ch])trie[p][ch]=cnt,p=fa[p];
        if(!p){
            fa[last]=1;return last;
        }
        int q=trie[p][ch];
        if(len[p]+1==len[q]){
            fa[last]=q;return last;
        }
        len[++cnt]=len[p]+1;
        for(int j=0;j<26;j++)trie[cnt][j]=trie[q][j];
        fa[cnt]=fa[q];fa[q]=cnt;fa[last]=cnt;
        while(trie[p][ch]==q)trie[p][ch]=cnt,p=fa[p];
        return last;
    }
    void build(){
        queue<int>q;
        for(int i=0;i<26;i++)if(T.trie[1][i])q.push(T.trie[1][i]);
        pos[1]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            pos[x]=ins(T.col[x],pos[T.fa[x]]);
            for(int i=0;i<26;i++)if(T.trie[x][i])q.push(T.trie[x][i]);
        }
    }
}SAM;
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        T.ins(s);
    }
    SAM.build();
    for(int i=2;i<=SAM.cnt;i++)ans+=SAM.len[i]-SAM.len[SAM.fa[i]];
    printf("%lld\n",ans);
    return 0;
}

注意写 dfs 的话复杂度是不对的，是 trie 上所有节点深度之和，平方级别。

在线构建

在线构建就是和 SAM 一样，每读入一个字符就插入一个字符。当然我们每次插入前需要初始化last指针。

实际上我们只需要在 SAM 的插入前面特判就行。首先我先把代码放上来。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char s[1000010];
int n;
long long ans;
struct Sam{
    int cnt,fa[2000010],len[2000010],trie[2000010][26];
    Sam(){cnt=1;}
    int ins(int ch,int last){
        if(trie[last][ch]){
            int p=last,q=trie[p][ch];
            if(len[p]+1==len[q])return q;
            else{
                len[++cnt]=len[p]+1;
                for(int i=0;i<26;i++)trie[cnt][i]=trie[q][i];
                while(trie[p][ch]==q)trie[p][ch]=cnt,p=fa[p];
                fa[cnt]=fa[q];fa[q]=cnt;
                return cnt;
            }
        }
        int p=last;last=++cnt;
        len[last]=len[p]+1;
        while(p&&!trie[p][ch])trie[p][ch]=cnt,p=fa[p];
        if(!p){
            fa[last]=1;return last;
        }
        int q=trie[p][ch];
        if(len[p]+1==len[q]){
            fa[last]=q;return last;
        }
        len[++cnt]=len[p]+1;
        for(int j=0;j<26;j++)trie[cnt][j]=trie[q][j];
        fa[cnt]=fa[q];fa[q]=cnt;fa[last]=cnt;
        while(trie[p][ch]==q)trie[p][ch]=cnt,p=fa[p];
        return last;
    }
}SAM;
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);int last=1,len=strlen(s+1);
        for(int j=1;j<=len;j++)last=SAM.ins(s[j]-'a',last);
    }
    for(int i=2;i<=SAM.cnt;i++)ans+=SAM.len[i]-SAM.len[SAM.fa[i]];
    printf("%lld\n",ans);
    return 0;
}

特判是用来处理已经存在这个转移的情况，需要分转移是否连续来讨论。

第一个特判：前面已经插入过相同的转移且转移连续，直接不管。

第二个特判：转移不连续，类似 SAM 的处理方式，我们同样需要把一个状态拆开变成两个。那么把原来的状态复制一份，把除了 \(\text{len}\) 以外的信息复制过去，重新标定 \(\text{len}\) 并且重定向转移边，和 SAM 是一样的。

根据论文，它的复杂度也是 trie 上所有节点深度之和级别的。所以有时候遇到题目给你一棵 trie 的题会爆炸。但是平时跑的飞快，比离线快一车。

应用继续咕。