后缀自动机 (SAM)

[Ir1d]

https://oi-wiki.org/string/sam/

[interestingLSY]

写得好好啊qwq

[nocrizwang]

大力支持

[Tgotp]

后排兹瓷

[PhoenixGS]

想知道在多个字符串间的最长公共子串中的算法的时间复杂度是$k\sum S_i$的吗？

[Ir1d]

@PhoenixGS 是呀

[Biscuit46]

写的很好啊!!!

[NagaseIori]

不考虑加一点广义SAM相关的内容吗qwq

[Ir1d]

@ajcxsu 好耶 欢迎来加

[ACfunction]

引理 1： 两个非空子串 和 （假设 ）的 相同，当且仅当字符串 是 的后缀。
这句话，不应该是包含于的关系吗。。为什么是相同

[longlongzhu123]

算法中的最后一项：

最终我们需要使用后缀链接从状态 $p$ 返回，因为存在一条通过 $p$ 到状态 $q$ 的转移，并在此过程中重定向所有状态到状态 $clone$。

此处翻译有误，英文翻译的原文为：

Finally we need to walk from the state p back using suffix links as long as there is a transition through c to the state q, and redirect all those to the state clone.

或应翻译成：

最终我们需要使用后缀链接从状态 $p$ 往回走（返回 ? ），只要存在一条通过 $p$ 到状态 $q$ 的转移，就将该转移重定向到状态 $clone$。

[longlongzhu123]

试着开个 pr qwq

[Ir1d]

@longlongzhu123 好耶！麻烦帮忙开个 pr 修一下呗 👍

[wolfdan666]

1. 建议sam_init将sz清理，并且在init和cur构建的时候清空map！（菜鸡debug一题两小时）
2. 建议不要使用map(菜鸡debug完又TLE了)

[ComeIntoCalm]

@ACfunction
引理 1： 两个非空子串 和 （假设 ）的 相同，当且仅当字符串 是 的后缀。
这句话，不应该是包含于的关系吗。。为什么是相同
确实是相同，非循环后缀的情况下....

[ShiinaMashiro19]

第一次出现的位置中：
$firstpos(cur)=len(cur)-1$
这个是因为字符串下标从$0$开始吗？

[Schwarzkopf-Henkal]

@Schwarzkopf-Henkal

@ce-amtic
SAM的时间复杂度和|Σ|有关吗

是的，但是一般把这个看作常数，要不然就是换成map或者unordered_map来达到变成一个log（更 劣 了）或者去掉的目的

但是 SAM 上转移边的数量还是线性的吧，那为什么时间复杂度会和字符集有关？

你在分裂节点的时候需要把原节点的连边复制一遍，暴力for或者memcpy都是O(|Σ|)的

[warzone-oier]

算法的描述有点问题。
最后往回走的时候，若不存在 $p$ 到 $q$ 的转移，直接退出
不这么写复杂度会错

[warzone-oier]

求出现次数还可以将 last 到根路径上的结点设为出现1次，然后在 SAM 上拓扑

[Aonynation]

写的很好啊!!!

[CodingJellyfish]

不用平衡树的 SAM 应该是 $O(n\left|\Sigma\right|)$ 的吧，瓶颈是复制节点。

[Singulet31258]

map内部实现就是平衡树，要加平衡树的话直接用map即可。

[Ya-kei]

可以 $O(n|\Sigma|)$ 空间换线性时间吧

[cly090327]

深度好文！！！

[quiet-yu]

引理2那里不应该是子集吗？为啥是真子集？也会有相等的情况呀？

[Ya-kei]

就是子集啊？

[Dreamerkk]

longest 的定义是啥？？？

[JYRowe]

请问 Wikipedia 上面有没有 SAM 的页面，检索失败

[cwl769]

现在有英文页面，但是没有中文的

[FlamingBlade-Offical]

应用 -> 出现次数。

“我们只需要考虑两个可能有相同 \operatorname{endpos} 值的不同状态。如果一个状态是由另一个复制而来的，则这种情况会发生。然而，这并不会对复杂度分析造成影响，因为每个状态至多被复制一次。”

这句话是错误的，不一定每一个状态只被复制一次。例如 aabbab。

[TaoRane]

资瓷

[Easonoi]

显然，SAM中的每个状态对应一个或多个endpos相同的子串。 这句话不太理解，怎么就显然了？

[rainlycoris]

对于 多个字符串间的最长公共子串 直接按照 两个字符串的最长公共子串 就好了吧。

把一个串拿去匹配，剩下的串各自建立 SAM，每次的匹配长度就是剩下的串各自匹配长度的 $\min$。

[Github-ZhangXingYu]

最后一个应用（多个字符串间最长公共子串）答案我感觉不太优，个人认为让剩下字符串去和第一个字符串的后缀自动机匹配更好（详见https://www.cnblogs.com/Jiaaaaaaaqi/p/10903614.html） ，这样空间上不用*k（字符串个数），时间上也更快。通过上面提到的方法和我提到的方法进行对比，在1e5数据量的时候，二者时间差>=10倍。

[visla-maxiangxiang]

后缀自动机的转移边的数量少于3n-4，那是否可以只开辟3n的空间来维护所有的转移边呢？为每个状态都用一个std::map来维护转移边的开销太大了。