概览

比较重要的概念：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://pst.iorinn.moe/archives/SAM.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议进行许可☆

网站

加入讨论吧...

推荐阅读

概览

Code

例 TJOI2015 弦论 /SPOJ SUBLEX

例 CTSC2012 熟悉的文章

例 BZOJ3473 字符串