本文改编自MAXimal :: algo :: Суффиксный автомат. Построение и применения的Google机翻版(什么玩意儿)

后缀自动机是一个处理字符串相关问题很有用的工具,例如检查一个字符串在另外一个字符串中是否出现过,计算一个字符串中不同子串的数量——它们都可以在线性时间内被解决。

从直观上看,后缀自动机保存着所有子串的信息,对于长度为n的字符串来说,它的后缀自动机只需要的空间,同时构造它的时间复杂度为

Continue reading