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

~~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$ [出处](https://cp-algorithms.com/string/suffix-automaton.html) 如果k很大，使用map存trans：时间$O(n\log n)$，空间$O(n)$（因为使用map，所以常数很大） 但是如果使用主席树实现$O(1)$继承trans，$O(\log n)$修改的话，时间复杂度应该还是$O(n\log n)$ ### GSAM-广义SAM（对Trie建） [PDF](https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/35395.pdf)或者看结尾 **当字符集的大小是不可忽略的时候。不能在Trie上建SAM** 好我们看[另一篇](http://dwjshift.logdown.com/posts/304570)： 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。 ```cpp 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。 实际写了一下，有很多需要注意的地方： 1. 这不是Trie树！会有重边！ 2. 因为S太长了（8e6）所以必须对Trie建立SAM，吧S放在上面跑。 3. 因为是广义后缀自动机，所以要拓扑排序。 ## [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树也不是最简状态自动机。