StringSuffixStructures I

一个关于后缀数组、后缀树和后缀自动机的题单,并且其中大多数题目是三者都可以做的。

首先是三道模板题,【模板】后缀自动机 (SAM) 和【模板】后缀排序 都是最基础的,而【模板】广义后缀自动机 由于不具有代表性、且 不能 起到卡掉错误时间复杂度做法和错误做法等原因,不太推荐(可以当水题水一水)。

接下来有几道真题,包括近年的 NOI 和多省联考,适合进行练习。

其余还收集了一些 Codeforces 上 3000 分左右以及洛谷主题库中的较难的 StringSuffixStructures 题目。


  1. P3809 - 【模板】后缀排序
  2. P3804 - 【模板】后缀自动机(SAM)
  3. P6139 - 【模板】广义后缀自动机(广义 SAM)
  4. P5284 - [十二省联考 2019] 字符串问题
  5. P4384 - [八省联考 2018] 制胡窜
  6. P4770 - [NOI2018] 你的名字
  7. P2178 - [NOI2015] 品酒大会
  8. P1117 - [NOI2016] 优秀的拆分
  9. P4022 - [CTSC2012] 熟悉的文章
  10. P4218 - [CTSC2010] 珠宝商
  11. CF1073G - Yet Another LCP Problem
  12. P5212 - SubString
  13. P5161 - WD与数列
  14. CF666E - Forensic Examination
  15. P5115 - Check,Check,Check one two!
  16. CF1063F - String Journey
  17. CF700E - Cool Slogans
  18. P6152 - [集训队作业2018] 后缀树节点数
  19. CF1266G - Permutation Concatenation
  20. CF1207G - Indie Album
  21. CF1037H - Security
  22. CF235C - Cyclical Quest
  23. CF204E - Little Elephant and Strings
  24. CF1043G - Speckled Band