简介

后缀自动机（SAM）我更愿称之为子串自动机，一个节点$u$ 代表多个互为后缀关系的串，其长度在 $len_{fail_u}$ 到 $len_u$，且出现的 endpos 集合相同。当前的新建的节点 $u$ 对应其实的是加入位置 $i$ 的一个后缀。$lst$ 维护的是以上一位结尾的最长后缀，其实就是 $s[1,n]$，这里感性理解就行，没必要揪着不放。

与 ACAM 一样，它的核心也是 fail 数组，$fail_u$ 表示的是当前 $u$ 代表的子串的一个最长真后缀，同时，SAM 维护了类似 ACAM 的 $tr$ 数组，其实现的功能是，$u$ 的所有串后加字符 $c$ 得到的串都在$tr_{u,c}$ 内。

引入

请你求出小写字符串 $S$ 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。

解法

构建出 SAM 之后，在 $fail$ 树上计算子树大小。

直接看代码吧！背背板子。

构建 SAM 的复杂度是 $O(n|\sum|)$，使用 $map$ 后是 $O(n\log|\sum|)$

code

const int N=2e6+5;int n,tr[N][26],cnt[N],fail[N],len[N],tot=1,lst=1;
string s;
int nxt[N],head[N];
ll ans;void ins(int x){int u=++tot,p=lst;len[u]=len[p]+1,cnt[u]=1;while(p && !tr[p][x]) tr[p][x]=u, p=fail[p];if(!p) fail[u]=1;else{int q=tr[p][x];if(len[q]==len[p]+1) fail[u]=q;else{int cq=++tot;len[cq]=len[p]+1;fail[cq]=fail[q];fail[u]=fail[q]=cq;memcpy(tr[cq],tr[q],sizeof(tr[q]));while(p && tr[p][x]==q) tr[p][x]=cq, p=fail[p];}}lst=u;
}void dfs(int u){for(int v=head[u];v;v=nxt[v]) dfs(v),cnt[u]+=cnt[v];if(cnt[u]>1) ans=max(ans,1ll*cnt[u]*len[u]);
}signed main(){                          IOS             cin>>s;n=s.length();s=" "+s;for(int i=1;i<=n;i++) ins(s[i]-'a');for(int i=1;i<=tot;i++) nxt[i]=head[fail[i]],head[fail[i]]=i;   dfs(1);cout<<ans<<"\n";return 0;
}

注意事项

SAM 的点数不超过 $2n-1$，边数（$tr$ 有效位置）据称不超过 $3n-4$，所以有关 SAM 的所有数组都要开 2 倍空间。
在写代码尤其是新建节点的时候，一定要看清每个相关数组是否赋值了。

应用

两个后缀的 LCP

对反串建 SAM，那么两个后缀的 lcp 就相当于 SAM 树上的 lca。

endpos 集合

对于一个前缀 $ s[1, i] $ 所对应的节点 $ u_i $，其会使得 $ u_i $ 的所有 fail 树祖先都在 $ i $ 处出现过。因此可以使用线段树合并维护每个节点对应的 endpos 集合，线段树维护的是该区间有多少个 endpos。

不同子串个数

$\sum_{u=1}^{tot} len_u-len_{fail_u}$。

走路操作

维护了长为 $l$ 的字符串 $t$，在 $s$ 正串 SAM 的 $u$ 节点，满足

\[len_{fail_u} < l \leq len_u: \]

后加字符 $c$：跳 $tr_{u,c}$
前删字符 $c$：如果 $l - 1 = len_{fail_u}$，则跳 $fail_u$，反之不动。
前加字符 $c$：如果 $l = len_u$，则跳至 $son_{u,c}$，反之不动，$son$ 其实是反向 $fail$。
$son_{u,c}$ 处理方法：枚举 $v$，$son_{fail_v,s[R(v)-len(u)]} = v$。

题目

CF235C Cyclical Quest

题目大意

给定一个文本串 $s$ 和若干个模式串 $t_i$，对于每个 $t_i$，求出 $s$ 中有多少个子串与它循环同构。

解题思路

将 $t_i$ 复制一份拼在一起，双指针在 SAM 上走路即可，只需要前删和后加。

CF700E Cool Slogans

题目大意

给定一个字符串 $s$，你需要求出一个最长的字符串序列，使得每一个串都在后一个串至少出现两次。

解题思路

首先总是可以让前一个是后一个的后缀，这样肯定不劣。建出 SAM，线段树合并维护 endpos。对 fail 树进行从上往下的贪心（其实也可以说是 dp，毕竟这是一个内向树）。

$u$ 后面能接 $v$（这里 $u$ 是 $v$ fail树上的父亲，即它的后缀）当且仅当在对于 $v$ 任意一个 endpos，因为 $u$ 对应的子串，肯定在 endpos 这个位置出现过，所以我们只需要判断在 $[endpos-len_v+1+len_u-1,endpos-1]$ 这个位置是否出现过即可。我们只需要找 $v$ 的任意一个 endpos，因为他们彼此之间是等价的。

日记详情

SAM 学习笔记

推荐资料

简介

引入

解法

注意事项

应用

两个后缀的 LCP

endpos 集合

不同子串个数

走路操作

题目

CF235C Cyclical Quest

题目大意

解题思路

CF700E Cool Slogans

题目大意

解题思路