后缀自动机

OI Wiki

一些重点：

  1. 后缀自动机形成的图是一个DAG（许多题可以利用这个性质DP）
  2. 这个DAG上的任意一条路径是一个子串
  3. endpos等价类可以由parent树的子树合并得到（再加上这个节点本身）
  4. 注意后缀自动机的源点代表空串，很多题需要单独处理
  • 例题：
  1. luogu P3804 【模板】后缀自动机 (SAM) 题解
  2. luogu P3975 [TJOI2015]弦论 题解
  3. SP1812 LCS2 - Longest Common Substring II 题解
由于博主比较菜，所以有很多东西待学习，大部分文章会持续更新，另外如果有出错或者不周之处，欢迎大家在评论中指出！
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/With-penguin/p/13341940.html