Manacher+回文自动机 专题训练 字符串 数学

Manacher+回文自动机 专题训练

本来计划着刷完网络流马上去博弈论的,可是做了两道题之后发现有点做不动了,就先花了半天来复习字符串,顺便把之前的坑都填上。 BZOJ2342 [Shoi2011]双倍回文 这道题用回文自动机应该是比较简单。因为满足要求的1/2回文串节点一定在当前节点的fail指针指向的祖先中,所以只需要建出回文自动机···
后缀数组 专题训练 字符串

后缀数组 专题训练

关于后缀数组的学习,还是费了不少精力的,尤其是一开始入门,连个模板都不理解,也不会基数排序,所以这个知识点从六月一直拖到了现在,有两篇专门讲后缀数组的文章,感觉还不错,我就是看了这俩之后才算入了门,转过来: 五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码) 后缀数组应用小结   之后···
BZOJ1030 文本生成器 && POJ2778 DNA Sequence  AC自动机 字符串

BZOJ1030 文本生成器 && POJ2778 DNA Sequence AC自动机

先上题目:   这俩题非常相似,给出文本串的长度和一些目标串,求所有经过/不经过单词节点的串的数量。 第一道题给的目标串数目多,而且比较长,所以在Trie树中节点数较多,而文本串长度较小,所以可以采用DP的思路搞出来:设f[i][j]:走了i步,当前在自动机上j号点时的方案总数。构建出tr···