SAM练习题

题单介绍

请配合 : [后缀自动机学习笔记(应用篇)](https://www.luogu.com.cn/blog/command-block/hou-zhui-zi-dong-ji-xue-xi-bi-ji-ying-yong-pian-post) 食用。 $$\text{智商不够,SAM来凑}$$ 本蒟蒻只会无脑SAM,哪位鸽鸽给咱教育一下SA啊? 涉及的知识点: - **自动机DAG和parent tree的意义** - **SAM与AC自动机的相似性** - **SAM构建反串后缀树** - **广义SAM** - **线段树合并维护endpos** - **SAM上树分治** 如果有相关的题目,欢迎私信本蒟蒻。(特别是带有新技巧的题目)

题目列表

  • 【模板】后缀自动机（SAM）
  • 不同子串个数
  • LCS - Longest Common Substring
  • [SDOI2016] 生成魔咒
  • [TJOI2019] 甲苯先生和大中锋的字符串
  • Fake News (hard)
  • JZPGYZ - Sevenk Love Oimaster
  • [TJOI2015] 弦论
  • [BJOI2020] 封印
  • [ZJOI2015] 诸神眷顾的幻想乡
  • Match & Catch
  • Three strings
  • Cyclical Quest
  • SubString
  • Paper task
  • [CTSC2012] 熟悉的文章
  • Little Elephant and Strings
  • [USACO17DEC] Standing Out from the Herd P
  • Security
  • [HEOI2016/TJOI2016] 字符串
  • REPEATS - Repeats
  • 区间本质不同子串个数
  • Forensic Examination
  • [十二省联考 2019] 字符串问题
  • [CmdOI2019] 口头禅
  • [NOI2018] 你的名字
  • String Journey
  • Cool Slogans
  • [八省联考 2018] 制胡窜
  • WD与数列
  • [BJWC2018] Border 的四种求法
  • Asterisk Substrings
  • Ж-function