一个关于后缀数组、后缀树和后缀自动机的题单,并且其中大多数题目是三者都可以做的。
首先是三道模板题,【模板】后缀自动机 (SAM) 和【模板】后缀排序 都是最基础的,而【模板】广义后缀自动机 由于不具有代表性、且 不能 起到卡掉错误时间复杂度做法和错误做法等原因,不太推荐(可以当水题水一水)。
接下来有几道真题,包括近年的 NOI 和多省联考,适合进行练习。
其余还收集了一些 Codeforces 上 3000 分左右以及洛谷主题库中的较难的 StringSuffixStructures 题目。