后缀自动机

Author Avatar
ajcxsu 2月21日
  • 59 次阅读

关于指针,它死了(悲)

推荐阅读

OIWIKI - SAM
SAM图片生成器
KesdiaelKen - SAM
CLJ的课件

基本上就是一个读不懂了就换一个,三个轮流看,但我个人认为第三篇是比较容易理解的(相对)。

概览

比较重要的概念:parent树(在OIwiki上直接被称为由$link$构成的树形结构)

比较重要的构建方法:增量法

比较重要的两个内容:len和fa(都是parent树里储存的数据,而parent树结构本身就储存了有关$endpos$等价类的信息)

比较重要的原理:$endpos$等价类(CLJ课件上是$right$集合)

以及板子比较好背

增量法增加的最重要的过程其实是parent树的变化。因为对于本来的SAM来说,其实会产生新转移的状态(或转移产生变动的状态)就只有包含旧串的后缀的状态。因此给不含转移的加上转移,给本来含有转移的状态该怎么转移做讨论,和对新状态的fa做讨论。

如果第一个找到的含有转移的状态,无论是改还是不改,讨论后都不需要再往上寻找,依托于对状态数和边数(边数的复杂度证明我不太懂)的复杂度分析,整个算法的复杂度都是正确的。感觉这个东西真的是相当的神仙。

虽然感觉我只能算理解了个大概。

Code

指针版MLE了。

#include<bits/stdc++.h>
using namespace std;

const int N=2e6+10;
int h[N<<1], to[N<<1], nexp[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
struct Node {
    int len, fa, ch[26];
} nd[N<<1];
int siz[N<<1];
int idx=1, lst=1;

void add(int c) {
    int p=lst, np=lst=++idx;
    siz[idx]=1;
    nd[np].len=nd[p].len+1;
    for(; p && !nd[p].ch[c]; p=nd[p].fa) nd[p].ch[c]=np;
    if(!p) nd[np].fa=1;
    else {
        int q=nd[p].ch[c];
        if(nd[q].len==nd[p].len+1) nd[np].fa=q;
        else {
            int nq=++idx; nd[nq]=nd[q];
            nd[nq].len=nd[p].len+1, nd[q].fa=nd[np].fa=nq;
            for(; p && nd[p].ch[c]==q; p=nd[p].fa) nd[p].ch[c]=nq;
        }
    }
}

char s[N];
long long ans;
void dfs(int x) {
    for(int u=h[x];u;u=nexp[u])
        dfs(to[u]), siz[x]+=siz[to[u]];
    if(siz[x]!=1) ans=max(ans, 1ll*siz[x]*nd[x].len);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>s;
    for(int l=0; s[l]; l++) add(s[l]-'a');
    for(int i=2; i<=idx; i++) ins(nd[i].fa, i);
    dfs(1), cout<<ans<<endl;
    return 0;
}

例 TJOI2015 弦论/SPOJ SUBLEX

引出来一些重要的推论。

按照$(len, idx)$的双关键字排序可以同时得到parent树和SAM上的拓扑序,避免了额外的建图。(这里绝大部分人使用了基排)

同时引出来parent树的节点的$endpos$集合大小的求解方法。

以及奇怪的贪心和卡空间。

例 CTSC2012 熟悉的文章

广义SAM+维护最大子串滑动窗口+二分+单调队列优化DP

说到广义SAM就是在每次插入新串之前设$lst=root$,至于为什么这样子可以我不知道...

例 BZOJ3473 字符串

广义SAM标记子串在各字符串中的出现次数。

我们通过一个串所到达的状态包含多个串,通过这个状态往$fa$上跳代表前往这些串的一些后缀。所以通过一个串到达的所有状态的所有$fa$就是所有前缀的所有后缀,也就是所有子串。

本文链接:https://acxblog.site/archives/SAM.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。