后缀自动机总结

后缀自动机

洛谷题单

前置芝士

后缀自动机1

后缀自动机2

后缀自动机3

广义后缀自动机

例题略解

P3804 【模板】后缀自动机 (SAM)

模板题,先按顺序把每一个压进去,然后按计数排序(就是SA里的那个)排一下序。

可以发现len的大小某种意义上就是该节点的深度,再用siz存一下,更新最大值就好了。

\(code\)

P4070 [SDOI2016]生成魔咒

为数不多的一看题面就有思路的紫题


不开 \(long long\)见祖宗


利用上述后缀自动机的树形结构。每个节点对应的子串数量是
\(len_i-len_{fa(i)}\),对于每一个节点直接求和就ok。然后我们愉快的TLE/MLE \(60pts\)

显然,许多节点在之前已经计算过,可以直接转移,如果在添加时改变了fa的值直接重新加一下这个点就好了,用一下map存ch。

\(code\)

P3975 [TJOI2015]弦论

和模板题有一定的联系还是先把每一个字符都压进去,
然后排序求出对应的siz值(每个字符在字串中出现的个数)。

在用一个sum数组记录一下子树及自身的siz和,对于T=0的情况直接把每个siz记录为1就好了,然后判断sum[1]与K的大小关系。

最后再递归输出就好了。

\(code\)

P6139 【模板】广义后缀自动机(广义 SAM)

板子题,用的是离线做法,在线做法懒得学 (其实是看不懂TAT)

思路比较好理解,无非就是把每个串压进字典树,然后bfs扫一遍加进SAM就好了。

  • 注意:开了long long见祖宗

\(code\)

P3346 [ZJOI2015]诸神眷顾的幻想乡

半个板子题,字串的数量把图里的每个点度为1的点向下扫一遍,放到字典树里,再跑一边广义后缀自动机就ok了。

  • 注意:字典树从1开始tmp一定要初始化成1.

\(code\)

P5546 [POI2000]公共串

SP1811 LCS - Longest Common Substring

SP1812 LCS2 - Longest Common Substring II

SP10570 LONGCS - Longest Common Substring

其实这几个题都是一个题。。。(可能也就是第二个比较简单一点吧)

大概思路就是先读入一个串。然后将剩下的每一个分别和他比对,然后求出一个maxn数组,maxn[i]表示i结尾的最大的匹配长度。

因为是记录多个串,因此我们应该对于所有的取最小值,存到minn数组里,
如果i点可以被匹配那么他在parent树上的任意一点都可以被匹配到,可得到一下以下式子:

\(\max(i)=\max\limits_{v\in son(u)}\{\min(mx(v),len(u))\}\)

然后再每个串后更新minn,最后找minn最大值就好了。(逃

\(code1\)

\(code2\)

\(code3\)

\(code4\)

P4248 [AHOI2013]差异

题目中的式子就是所有后缀两两除公共前缀外的长度。

还是先初始化,然后计数排序求一下siz数组(siz[i]表示以i节点开头的不同字串的数量)

  • 递推式子:

$\sum\limits_{i=tot,now=A[i]}^{1}tre[now].len-tre[tre[now].fa].len)siz[now](n-siz[now]) $

前半部分就是求不同字串的个数(长度),后面就是排列组合,
以i开头的有siz[i]个,和剩下的n-siz[i]个的组合数显然就是\(siz[now]*(n-siz[now])\)

  • 注意:理论上来讲本题应该反着建后缀自动机,将前缀化为后缀,但是观察题面不难发现求前缀和后缀是差不多的。。。

\(code\)

P1368 【模板】最小表示法/工艺

本来应该是一个最小表示法的题,但是拿SAM也能做 (主要是懒得学)

SAM的话就是最小循环移位的板子题了,先把环化串,把串插进去两次。然后就对于每一层取最小的字典序的就可以了,共取n层。

\(code\)

P2178 [NOI2015] 品酒大会

我真傻,真的,我单知道要反转字符串,却把反转打在了读入前面TAT

先是对于这个串建后缀自动机(建的时候要存一下这个节点在原来字符串中的位置),然后求出siz,siz大于1时把now与fa[now]差分存一下\(\frac {(siz[now]-1)\times siz[now]}2\),也就是\(C_{siz[i]}^{2}\)算出r相似的总数,顺便再更新一下配酒之后的美味度(好像是叫这个名字)。

最后再用前缀和把差分给搞回去,美味度依次求最值就好了

  • 注意:要把最大与次大,最小与次小分别相乘比较(之前SA里面好像也说过)

\(code\)

P4022 [CTSC2012]熟悉的文章

SAM+二分答案+单调队列优化dp

乍一看,这题挺花里胡哨,再定睛一看,就是挺花里胡哨。

和前面的那个公共串有一点相似,先把文本串压 SAM (建不建 Tire 都差不多)然后对于每一个进行一下匹配。
以 num[i] 表示以第 i 个结尾的与文本串的最长公共字串的长度。

以 f[i] 表示前i个字符的字串中可以匹配的最长的长度,可以得到以下式子:

\(f[i]=\max (f[i-1],f[j]+i-j)\)

满足条件:\((i-j \ge L)\) 并且 \(s[j+1..i]\) 能够匹配.

显然,可以采用单调队列来优化

while(head<=tail&&f[q[tail]]-q[tail]<=f[i-mid]-(i-mid))
  tail--;

根据式子,把不优于现在的解的给提出队列,

while(head<=tail&&q[head]<i-num[i])
  head++;

把超出范围的给干掉。
如果队列还有数的话,更新就好了。
\(code\)

P4770 [NOI2018] 你的名字

参考题解,懒得写了 (其实是不太会)

\(code\)

码完之后试着改了一下码风,自我感觉良好,这里

上一篇:加密算法的使用场景


下一篇:什么是哈希算法,如何计算?