后缀自动机（SAM）学习笔记 | ouuan的博客

[ouuan]

https://ouuan.github.io/%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88SAM%EF%BC%89%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

后缀自动机是一种处理字符串问题的有力工具（废话），它的码量不比后缀数组大（实际代码难度不比后缀数组小，但也不难），处理问题时的思维难度往往比后缀数组小，虽然常数略大，但复杂度是 $O(n)​$ 的。（实际上，若字符集大小为 $|\Sigma|​$，则：时间复杂度 $O(n)​$，空间复杂度 $O(n|\Sigma|)​$ 或时间复杂度 $O(n\log|\Sigma|)​$，空间复杂度 $O(n)

[ButterflyDew]

orz ouuan

[GaisaiYuno]

otz