字符串

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

Manacher+回文自动机 专题训练

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

后缀数组 专题训练

关于后缀数组的学习,还是费了不少精力的,尤其是一开始入门,连个模板都不理解,也不会基数排序,所以这个知识点从六月一直拖到了现在,有两篇专门讲后缀数组的文章,感觉还不错,我就是看了这俩之后才算入了门,转过来: 五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码) 后缀数组应用小结   之后···
BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash 字符串

BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash

题意就是给出字符串,动态插入、修改字符。我们需要数据结构,动态维护序列的哈希值。 $$H(l,r)=\sum _{i=l} ^{r} S[i]*base^{i-l}$$ 考虑这个计算一段字符串hash值的公式,可以通过维护子树hash值,再利用Treap的分裂合并操作动态维护,最后二分答案就好啦。 ···
BZOJ3676 [Apio2014]回文串 回文自动机 字符串

BZOJ3676 [Apio2014]回文串 回文自动机

回文自动机裸题。 空间复杂度:O(n*(字符集大小)),时间复杂度:O(n*log(字符集大小))。 可实现的操作: 1.求字符串前缀中本质不同的回文串的个数。 2.求每一个本质不同回文串出现的次数。 3.求所有的回文串数。 4.求以特定下标为结尾的回文串数。 同时求出回文串的长度。 直接上代码,具···
BZOJ1030 文本生成器 && POJ2778 DNA Sequence  AC自动机 字符串

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

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