【字符串】后缀系列

收集了大量的后缀数组, 后缀自动机的题目 如果你有好题或题单编排不合理和其他问题可以私信我 **Update on 2020/9/16:修改排版及部分内容** [不要脸的推荐自己的blog](https://www.cnblogs.com/Hs-black/p/12004609.html) * **Update on 2020/3/29 增加一些题目说明** * **Update on 2021/6/10 删去若干重题模板题，增加若干进阶题目** ## 模板 * [后缀数组](https://www.luogu.com.cn/problem/P3809) * [后缀自动机](https://www.luogu.com.cn/problem/P3804) **以下题目有可能两种做法都可做(用$标记), 部分后缀数组题目可以拿hash水(例如求lcp)** * $[[JSOI2007]字符加密 ](https://www.luogu.com.cn/problem/P4051) SA模板题直接倍长求SA即可 * $[SP694](https://www.luogu.com.cn/problem/SP694) 求本质不同字串个数 * $[SP705](https://www.luogu.com.cn/problem/SP705) 上题双倍经验 * [SP8222](https://www.luogu.com.cn/problem/SP8222) 后缀自动机基础题 * $[[TJOI2017]DNA](https://www.luogu.com.cn/problem/P3763) 直接后缀数组求三次lcp, 常数较大, 可以用hash, 也有多项式解法 * [[SDOI2016]生成魔咒](https://www.luogu.com.cn/problem/P4070) sam在线查询不同字串个数, 较易 * [SP1811](https://www.luogu.com.cn/problem/SP1811) 两串最长公共字串长度, 直接在后缀自动机上跑就行 * [SP1812](https://www.luogu.com.cn/problem/SP1812) 多串lcs, 上一题加强版, 记录后缀自动机节点匹配情况的信息即可 * [SP7258](https://www.luogu.com.cn/problem/SP7258) 求本质不同字典序第k大串, TJOI弦论子问题 * [SP10570](https://www.luogu.com.cn/problem/SP10570) 多组数据成黑题?QAQ * [[TJOI2015]弦论](https://www.luogu.com.cn/problem/P3975) 后缀自动机求第k大字串, 比较基础但考验对sam的理解 * $[[AHOI2013]差异](https://www.luogu.com.cn/problem/P4248) 后缀数组+笛卡尔树或用sam亦可解之 * $[[HAOI2016]找相同字符](https://www.luogu.com.cn/problem/P3181) 直接在后缀动机上匹配并记录前缀和即可 * [[NOI2016]优秀的拆分](https://www.luogu.com.cn/problem/P1117) 听说暴力95? 用SA判断有无重复子串, 其实是比较妙的题 * $[[NOI2015]品酒大会](https://www.luogu.com.cn/problem/P2178) SA+并查集 * [[USACO17DEC]Standing Out from the Herd P](https://www.luogu.com.cn/problem/P4081) 广义后缀自动机裸题 * [[ZJOI2015]诸神眷顾的幻想乡](https://www.luogu.com.cn/problem/P3346) 广义后缀自动机裸题 * [SP8093](https://www.luogu.com.cn/problem/SP8093) 查询串是多少模板串的字串, 可以ac自动机或广义sam, 转化为区间数颜色即可 * [P5212](https://www.luogu.com.cn/problem/P5212) 在线询问一个串在模板串中出现了几次，后缀自动机套上LCT即可 * [P6292](https://www.luogu.com.cn/problem/P6292) 查区间本质不同子串个数，这样的题可以离线按右端点排序，用后缀自动机和lct维护，每个节点打上最近的颜色，lct可以很好的维护 由于本人太弱了, 暂时写了一些基础题, 以后写了新题再更⑧(咕咕咕