【字符串】后缀系列

收集了大量的后缀数组, 后缀自动机的题目

如果你有好题或题单编排不合理和其他问题可以私信我

Update on 2020/9/16:修改排版及部分内容 不要脸的推荐自己的blog

• Update on 2020/3/29 增加一些题目说明
• Update on 2021/6/10 删去若干重题模板题，增加若干进阶题目

模板

• 后缀数组
• 后缀自动机

以下题目有可能两种做法都可做(用$标记), 部分后缀数组题目可以拿hash水(例如求lcp)

• ](https://www.luogu.com.cn/problem/P4051) SA模板题直接倍长求SA即可

• SP8222 后缀自动机基础题

• [SDOI2016]生成魔咒 sam在线查询不同字串个数, 较易

• SP1811 两串最长公共字串长度, 直接在后缀自动机上跑就行

• SP1812 多串lcs, 上一题加强版, 记录后缀自动机节点匹配情况的信息即可

• SP7258 求本质不同字典序第k大串, TJOI弦论子问题

• SP10570 多组数据成黑题?QAQ

• [TJOI2015]弦论 后缀自动机求第k大字串, 比较基础但考验对sam的理解

• [NOI2016]优秀的拆分 听说暴力95? 用SA判断有无重复子串, 其实是比较妙的题

• [USACO17DEC]Standing Out from the Herd P 广义后缀自动机裸题

• [ZJOI2015]诸神眷顾的幻想乡 广义后缀自动机裸题

• SP8093 查询串是多少模板串的字串, 可以ac自动机或广义sam, 转化为区间数颜色即可

• P5212 在线询问一个串在模板串中出现了几次，后缀自动机套上LCT即可

• P6292 查区间本质不同子串个数，这样的题可以离线按右端点排序，用后缀自动机和lct维护，每个节点打上最近的颜色，lct可以很好的维护

由于本人太弱了, 暂时写了一些基础题, 以后写了新题再更⑧(咕咕咕

1. P3804 - 【模板】后缀自动机（SAM）
2. P3809 - 【模板】后缀排序
3. P4051 - [JSOI2007] 字符加密
4. SP705 - SUBST1 - New Distinct Substrings
5. SP8222 - NSUBSTR - Substrings
6. P3763 - [TJOI2017] DNA
7. P4070 - [SDOI2016] 生成魔咒
8. SP1811 - LCS - Longest Common Substring
9. SP1812 - LCS2 - Longest Common Substring II
10. SP7258 - SUBLEX - Lexicographical Substring Search
11. P3975 - [TJOI2015] 弦论
12. P4248 - [AHOI2013] 差异
13. P3181 - [HAOI2016] 找相同字符
14. P1117 - [NOI2016] 优秀的拆分
15. P2178 - [NOI2015] 品酒大会
16. P4081 - [USACO17DEC] Standing Out from the Herd P
17. P3346 - [ZJOI2015] 诸神眷顾的幻想乡
18. SP8093 - JZPGYZ - Sevenk Love Oimaster
19. P4770 - [NOI2018] 你的名字
20. P2463 - [SDOI2008] Sandy 的卡片
21. P4022 - [CTSC2012] 熟悉的文章
22. CF666E - Forensic Examination
23. CF1063F - String Journey
24. P5212 - SubString
25. P6292 - 区间本质不同子串个数
26. P6152 - [集训队作业2018] 后缀树节点数
27. CF700E - Cool Slogans
28. P5576 - [CmdOI2019] 口头禅
29. P5546 - [POI 2000 R3] 公共串
30. CF1037H - Security
31. CF235C - Cyclical Quest
32. CF204E - Little Elephant and Strings
33. CF802I - Fake News (hard)
34. CF873F - Forbidden Indices