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