SAM-后缀自动机-个人总结

i207M · 2018-11-16 14:43:07 · 个人记录

~~JZ入门题：在SAM上跑SG函数~~

~~感觉SAM写起来比AC自动机还简单~~

~~然后考试的时候就忘了AC自动机~~

写SAM的时候细节还是挺多的，一定要随时用眼睛看

SAM初始的tot要设为1！！！

看12月集训Day2.

因为很重要，所以写在前边。

设k为字符集大小。

普通的SAM（一个串的SAM）

如果每个点的trans数组开成字符集大小：时间O(n)，空间O(nk)

此时：

SAM中的状态总数（right集合相同为一个state）上界：2n-1，达到方法：abbbb...bbb

SAM中的转移总数上界：3n-4，达到方法：abbb...bbbc

出处

如果k很大，使用map存trans：时间O(n\log n)，空间O(n)（因为使用map，所以常数很大）

但是如果使用主席树实现O(1)继承trans，O(\log n)修改的话，时间复杂度应该还是O(n\log n)

GSAM-广义SAM（对Trie建）

PDF或者看结尾

当字符集的大小是不可忽略的时候。不能在Trie上建SAM

好我们看另一篇：

k为字符集。

用BFS离线建：时空O(nk)

用DFS在线建：时间O(nk+dfs)，空间不变。

SAM的处理，往往和可持久化线段树合并维护right集合有关

把所有子串按照字典序大小输出

建好SAM后直接按字典序dfs一遍。

求字典序第k小子串

SPOJ SUBLEX

重复的子串不多次计数。

注意到后缀自动机中，虽然一个结点可能被当成多个结点的儿子，但这些连边都是满足拓扑序的，就是说，可以预处理出到达某个结点时，往下走可以得到多少个字符串，这样的预处理用拓扑排序+递推即可。这样的话，询问就是O(n)的复杂度。

在写这道题时，我在纠结如何预处理这个size，甚至想要去重，但是因为一条路径就唯一对应一个子串，因此我们统计的其实是一个点之后的路径条数，直接拓扑排序+DP即可。

但如果重复的子串多次计数呢？[TJOI2015]弦论

很简单，之前的方法是从每个节点必有一个子串产生，而现在每个点有多个子串产生，是多少？是right集合的大小！于是同样的做法就行了。

size不要和上一个算法弄混！求right集合时只给主干点+1。

一定要按拓扑序DP！

记得加上每个点的贡献。跑答案的时候，记得每走过一个边就要--k，因为有一个子串在这里结束了。

求多个串的最长公共子串

首先选出第一个串，建立SAM，然后我们要把其他串放到SAM上跑，方式和AC自动机很像，我们把parent树看作fail树，如果这个点没有这个儿子，就跳fa，同时更新len。

然后如果跳到了有这个儿子的节点，就++l（l表示已经匹配的长度），x变成儿子；

否则从rt开始重新跑。

然后考虑多串：我们其实是把每个点的匹配长度取min之后就是答案。于是我们维护每一个串的匹配的最长长度，然后和len和之前的min取min。

    for(ri i=1; i<=n; ++i)
    {
        int t=s[i]-'a';
        while(x&&!ch[x][t]) x=fa[x],l=len[x];
        if(x) ++l, x=ch[x][t];
        else x=rt,l=0;
        mx[x]=max(l,mx[x]);
    }

字符串的最小表示法

但是明明有更好写的双指针啊，而且不在意字符集大小。

大字符集非要用SAM？map！嫌弃map的复制太慢？~~主席树~~弃疗！

求本质不同的子串数量

就是每个点的\max -\min +1，怎么求min？\min=len[fa]+1！

字符串题，多组数据有关数组一定要清空干净！最好字符串char数组也memset一下

求多个数字字符串本质不同的子串的数字和

hdu4436

多个字符串？把每个字符串用特殊字符（比如10）接起来，跑一边SAM，建出DAWG，然后考虑DP：

我们不能走10边；对于根节点不能走0边，因为忽略前导零！然后维护从根节点到点x的方案数cnt和数字和sum，转移的话：sum[ch[x][i]]+=sum[x]\times 10+cnt[x]\times i。

其实不用特殊字符接起来也行，直接建广义SAM跑就可以了，很快。

[AHOI2013]差异

\displaystyle \sum_{1\leqslant i<j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)

一个很简单的方法是求出Height数组之后，这个问题就转化为了[2,n]的所有子区间的最小值的和，可以通过单调栈求出每个点作为最小值的区间，然后统计贡献。记得单调栈一边是>一边是>=

如果非要用SAM怎么办？Parent树的LCA实际上是两个前缀的最长公共后缀，所以我们需要对反串建立SAM，然后两个点的LCA就是最长公共前缀，DP计数一下就可以了。

[APIO2014]回文串

~~开O2防MLE？？？~~

Manacher和SAM的优秀结合！

首先建SAM，然后跑Manacher，得到若干本质不同的回文子串，然后我们要查询它们的出现次数，怎么查？子串S[l...r]的出现次数就是SAM上r对应的节点的祖先中，len>=r-l+1且最浅的祖先，这就是它的出现次数。

[USACO17DEC]Standing Out from the Herd

好题，专门写一个。

[ZJOI2015]诸神眷顾的幻想乡

求树上所有路径的不同子串个数，叶子数量<=20，N<=1e5

本来想20\times 20的枚举两个叶子然后把树上路径塞进去，看题解之后恍然大悟：直接从每个叶子出发遍历一棵树，然后把路径插入广义SAM就可以了！

SP8093

给定n个模板串，以及m个查询串，依次查询每一个查询串是多少个模板串的子串。

我们给SAM上每个点一个颜色，那么问题就转化成了一个点的parent树的子树的颜色个数，可以用dsu on tree或者树状数组+扫描线解决。

串

现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。

像上一题一样进行预处理，然后把每个串放在上面跑，如果一个点的次数小于k就不停的跳fa，然后答案累加上len[x]即可。

由于一步只能向下走1，所以复杂度是有保证的。这道题我为了加快，写了一个倍增，挂掉了，很奇怪。

CF666E Forensic Examination

SAM+数据结构

CF700E Cool Slogans

思维好题

BZOJ3796 Mushroom追妹纸

见另一篇博客。

pty的字符串

先把S建出SAM，求出每个点的rigth集合的大小，然后把Trie树放到SAM上跑，每经过一次一个点就把这个点的cnt++，然后求cnt在parent树上的子树和，答案即为\sum size_{right}\times sum_{cnt}\times (len[i]-len[fa[i]])

但是这个是不对的！因为匹配到一个点时，匹配的长度不一定是这个点的len，所以这个点的贡献要特殊计算，贡献的最后一部分为匹配的ml-len[fa[i]]。这样cnt只需要给fa加cnt。为什么fa及祖先就不用特殊考虑？因为它们的len一定小于ml。

实际写了一下，有很多需要注意的地方：

这不是Trie树！会有重边！
因为S太长了（8e6）所以必须对Trie建立SAM，吧S放在上面跑。
因为是广义后缀自动机，所以要拓扑排序。

[SCOI2012]喵星球上的点名

见另一篇博客。

CF1063F

一眼看上去是一个神题，但是用到的算法并不难。

我们把串反过来，序列也反过来。

首先，我们每次选出来的串，一定一个是另一个的后缀或前缀。换句话说，我们的序列从前到后长度依次递增。

设dp[i]表示以i结尾的序列的最长长度。考虑如何求出dp[i]。首先这个满足二分的性质，考虑check。因为我们已经知道，它的前一个一定是前缀或者后缀，于是我们枚举两种情况。剩下的就是求一个串出现的所有位置的dp值最大值了，对Parent树的dfs序建线段树即可。

我们发现，我们能够用来更新dp值的位置右端点也是单调不减的，于是用一个指针维护即可。

先丢定义：

结论：

说人话：

定义k阶GSAM为：最小的k使得取出原来所有串的后k个字符，它们两两不同。n为字符串个数。

则最简k-GSAM的时空复杂度均为O(\sum len+kn)。

但是Trie树上的串，虽然两两的后缀都不同，貌似k=1，但是！按Trie建出来的不是最简的GSAM！因为会有很多重合的情况！况且Trie树也不是最简状态自动机。