2012年noi冬令营陈立杰讲稿——SAM后缀自动机 后缀自动机Suffix Automaton; 吐槽&回答;先让我们看SPOJ上的一道题目;一个简单的做法;看起来很简单。。但是。。。;我们可以看到大部分人都TLE了。。为什么呢？;新的算法;OI中使用的字符串处理工具;什么是自动机;trans(s,str);;后缀自动机的定义;最简单的实现;最简状态后缀自动机;分析;分析;分析;分析;状态数的线性证明;状态数的线性证明;状态数的线性证明;一些性质;;一些性质;关于子串的性质;关于子串的性质; 线性构造算法; 定义和性质的回顾; 定义的回顾; 定义的回顾; 每个阶段; 每个阶段;每个阶段;每个