后缀自动机

Author Avatar
空気浮遊 2019年02月21日
  • 在其它设备中阅读本文章

关于指针,它死了(悲)

推荐阅读

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$ 就是所有前缀的所有后缀,也就是所有子串。