后缀自动机小结

还没写完后缀自动机就来写小结了

其实是莫比乌斯又推不下去了

一,板子

  其实还是迪哥的hhh

二,瞎写

  1,有关新建节点的几种分类讨论要记住,大概$yy$板子还是可以用的

  2,前缀节点指的是当前点所代表的$endpos$集合所对应的串中有一个原串的前缀。

     具体来说就是新建的$p$节点

  3,如果维护树形结构的话一般是$parent$树,具体的$fa$也是指的树上的$fa$

  4,“一个$endpos$集合对应多个不同长度的串,长度连续”可以用来求什么串的个数

  5,广义后缀自动机

三,题解包

  《生成魔咒》:

      据说是最板子的,求每次加入一个点的本质不同子串个数总和

      刚好运用到上文结论,每次多出来的就是新建节点最长子串长度-最短子串长度

      其实写的时候并不是这个而是另外一种更麻烦的方法

  《工艺》:

      可以将串开头的字母放到串末尾,然后求最小字典序

      长度翻倍之后在$SAM$上暴力找字典序最小即可

  《公共串》:

      求给定几个串的最长公共子串

      暴力建出一个串的$SAM$,然后在上面跑,失配就跳父亲

      一个比较重要的点就是要向父节点上传,因为你可能并没有经过父节点但是匹配上了

      因为父节点是儿子的后缀

  《弦论》:

      求第$K$小子串,两问,一个是本质不同,一个是本质相同。

      本质不同建出$SAM$跑就可以

      本质相同需要维护$endpos$集合,因为出现了多次所以做多次贡献

      关于维护$endpos$,对于每个前缀节点,在向儿子划分集合的时候会丢掉那个前缀所对应的点

      感性理解一下即可,所以每个前缀节点的集合大小初值为$1$,然后$topu$合并即可

  《诸神眷顾的幻想乡》:

      广义$SAM$

      具体构建和普通$SAM$类似,先建出$trie$树,然后记录当前点$lst$,回溯时改回去就行。

      然后题目特点是只有$20$个叶子节点,所以我们可以每个叶子扫一边来保证不漏

  《品酒大会》:

      肛道理这题用$SAM$真好做

      在$parent$树上倒序$topu$更新即可

  《Cheat》:

      挺好的题

      首先我们发现$L_0$具有单调性,所以我们二分,难点在于$check$。

      设f[i]为到达第i个位置总共匹配了多少,$g[i$]为第i个位置与之前最多能匹配多少。

      我们可以得到dp柿子:$f[i]=maxlimits_{i-g[i]leq jleq i-mid}{f[j]+i-j}$。      

      关于为什么要多一个$g$是因为复杂度。

      在$SAM$上乱跳时我们肯定选择最优的,失配时直接跳父亲,但是决策点不能保证从最靠前的点最优。

      加入$g$数组之后我们就可以用单调队列优化。

  《substring》:

      $SAM+LCT$,可以说是板子题,但是是没见过的板子,挺恶心。

大概就是这样

原文地址:https://www.cnblogs.com/MouDing/p/12113071.html