字符串

字符串菜菜，把学习过程中的字符串好题都放在这里。 本题单包含的内容：**字符串 hash、最小表示法、manacher、KMP 和 exKMP、trie 和 AC 自动机的简单应用**。适用人群：**提高+/省选-** ~~这题单怎么五颜六色的~~，保证了主要难度为蓝到紫，请放心食用。 关于学习路线。可以按照如下顺序刷模板，然后在刷模板的过程中穿插一些例题。 - [P3370 【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370) 字符串哈希绝对是入门良选 - [P1368 【模板】最小表示法](https://www.luogu.com.cn/problem/P1368) 有兴趣可以了解玩玩 - [P3805 【模板】manacher算法](https://www.luogu.com.cn/problem/P3805) 先从 Manacher 开始了解字符串算法的精髓 - [P3375 【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375) 短小但是精炼难懂，建议认真理解 - [P5410 【模板】扩展 KMP（Z 函数）](https://www.luogu.com.cn/problem/P5410) 思路一脉相承 - [P2580 于是他错误的点名开始了](https://www.luogu.com.cn/problem/P2580) Trie 树的简单入门题 - [P3808 【模板】AC自动机（简单版）](https://www.luogu.com.cn/problem/P3808) 可以开始 AC 自动机了 - [P3796 【模板】AC自动机（加强版）](https://www.luogu.com.cn/problem/P3796) 第一个加强版 - [P5357 【模板】AC自动机（二次加强版）](https://www.luogu.com.cn/problem/P5357) 第二个加强版，涉及到 fail 树的理解 下面是例题推荐，**难度不一定递增但大致按照难度排序，请自行食用，难的题可以等理解深刻了再回来做** ### Manacher Manacher 的精髓在于重复利用已经计算过的信息，后面的 KMP/exKMP 与其其实是异曲同工之妙。 首先肯定是需要打完模板的。下面的这些题有些可能有点巧妙，需要多思考思考。 - [P1659 [国家集训队]拉拉队排练](https://www.luogu.com.cn/problem/P1659) 不错的入门题 - [P3501 [POI2010]ANT-Antisymmetry](https://www.luogu.com.cn/problem/P3501) 比较裸 - [UVA11475 Extend to Palindrome](https://www.luogu.com.cn/problem/UVA11475) 需要稍微想一想 - [P6216 回文匹配](https://www.luogu.com.cn/problem/P6216) 统计答案十分精妙 - [P4555 [国家集训队]最长双回文串](https://www.luogu.com.cn/problem/P4555) 回文树可做，但是思考 $O(n)$ 做法大有裨益。 - [P5446 [THUPC2018]绿绿和串串](https://www.luogu.com.cn/problem/P5446) Manacher 好题 ### KMP/Hash/exKMP 这些题的解法有些多变，有的既可以 KMP 又可以 Hash 做。 首先是 KMP 的例题，打完板子之后首先要会的就是 KMP 怎么求字符串的周期，对于深入理解 KMP 有帮助，然后 fail 树等相关也肯定是需要掌握的 - [CF126B Password](https://www.luogu.com.cn/problem/CF126B) 稍微想想就可以做了 - [P4391 [BOI2009]Radio Transmission 无线传输](https://www.luogu.com.cn/problem/P4391) 周期 - [UVA10298 Power Strings](https://www.luogu.com.cn/problem/UVA10298) 还是周期 - [P3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) 又是周期，只是需要动动脑 - [UVA11022 String Factoring](https://www.luogu.com.cn/problem/UVA11022) 区间 dp，使用 KMP 找循环节进行转移优化 - [CF526D Om Nom and Necklace](https://www.luogu.com.cn/problem/CF526D) 自己思考 - [P4824 [USACO15FEB]Censoring S](https://www.luogu.com.cn/problem/P4824) 自行思考一下做法 - [P2375 [NOI2014] 动物园](https://www.luogu.com.cn/problem/P2375) 可以通过这题了解一下 fail 树 - [P5829 【模板】失配树](https://www.luogu.com.cn/problem/P5829) fail 树的模板，理解了之后其实非常简单 - [CF1200E Compress Words](https://www.luogu.com.cn/problem/CF1200E) 比较巧妙的把问题转化为使用 KMP - [P7114 [NOIP2020] 字符串匹配](https://www.luogu.com.cn/problem/P7114) Z 算法好题，需要对周期有比较深的理解 - [P3426 [POI2005]SZA-Template](https://www.luogu.com.cn/problem/P3426) 毒瘤 DP 题，需思考 border 的性质 - [CF808G Anthem of Berland](https://www.luogu.com.cn/problem/CF808G) 仍然是 dp 题 - [P3193 [HNOI2008]GT考试](https://www.luogu.com.cn/problem/P3193) KMP 与矩阵优化 dp - [P4503 [CTSC2014]企鹅QQ](https://www.luogu.com.cn/problem/P4503) 字符串 hash 的应用 - [P3538 [POI2012]OKR-A Horrible Poem](https://www.luogu.com.cn/problem/P3538) hash 与循环节，经典问题 - [P4036 [JSOI2008]火星人](https://www.luogu.com.cn/problem/P4036) 用平衡树维护 hash 值 ### Trie/AC 自动机 这里不考虑 01-Trie，下面是一些用到 Trie 了的的例题 - [SP4033 PHONELST - Phone List](https://www.luogu.com.cn/problem/SP4033) 几乎板题 - [UVA1401 Remember the Word](https://www.luogu.com.cn/problem/UVA1401) Trie 上 dp - [UVA11732 "strcmp()" Anyone?](https://www.luogu.com.cn/problem/UVA11732) Trie 与计数问题 - [P7469 [NOI Online 2021 提高组] 积木小赛](https://www.luogu.com.cn/problem/P7469) Trie 的一个简单应用，当然 hash 也可 然后是 AC 自动机，AC 自动机一是可以与 DP 结合，因为 Trie 的一个节点就是一个很好的 dp 状态，然后转移也比较方便；二是可以结合 fail 树然后套上其它的数据结构。确保先刷完三个模板以及学习完对应的数据结构（dfs 序，树链剖分等）。 - [P3966 [TJOI2013]单词](https://www.luogu.com.cn/problem/P3966) 模板 - [P3121 [USACO15FEB]Censoring G](https://www.luogu.com.cn/problem/P3121) AC 自动机 + 栈 - [P3041 [USACO12JAN]Video Game G](https://www.luogu.com.cn/problem/P3041) AC 自动机与简单 dp - [P4052 [JSOI2007]文本生成器](https://www.luogu.com.cn/problem/P4052) ACAM + dp，考虑一下补集思想。 - [P3311 [SDOI2014] 数数](https://www.luogu.com.cn/problem/P3311) ACAM + 数位 dp - [P2414 [NOI2011] 阿狸的打字机](https://www.luogu.com.cn/problem/P2414) 涉及到 fail 树，建议先学会树链剖分 - [CF163E e-Government](https://www.luogu.com.cn/problem/CF163E) 和上题类似 - [CF1207G Indie Album](https://www.luogu.com.cn/problem/CF1207G) 与阿狸的打字机类似 - [P2444 [POI2000]病毒](https://www.luogu.com.cn/problem/P2444) 理解了 ACAM 之后其实很简单 - [CF1202E You Are Given Some Strings...](https://www.luogu.com.cn/problem/CF1202E) 较巧妙的统计答案方法 - [P2292 [HNOI2004]L语言](https://www.luogu.com.cn/problem/P2292) 正解是一个使用状压优化的严格线性 dp - [CF696D Legen...](https://www.luogu.com.cn/problem/CF696D) 矩阵快速幂优化 ACAM 的 dp - [P5840 [COCI2015]Divljak](https://www.luogu.com.cn/problem/P5840) 树上差分做树链并，当然线段树合并也可做，[题解](https://blog.imyangty.com/sol-luogu-p5840/)