@[一扶苏一](/user/65363) emm看到这个贴有点想法就来回复了
本人基本用 map。几点：
- map版构造SAM的时间复杂度为 $O(n\log|\Sigma|)$。然而在拆点时，数组版的需要一次复制 $|\Sigma|$ 个信息，而 map 版的不会复制这么多无用信息。也许偶尔有时候 map 会比数组快。
- 在扫描 所有的 的转移时，数组仍然是一次 $O(|\Sigma|)$，但 map 版，同样的，避免了无用信息，数组的还要判断有没有这个转移（map 遍历一次应该不带log吧）。而且 map 方便，直接可以迭代器（C++11 auto更方便）。
- 在 $|\Sigma|$ 很大时，map 显然是最佳选择（生成魔咒）
- map 空间 $O(n)$，数组空间 $O(n \log |\Sigma|)$
以上使本人经常使用 map 的原因。但两种写法掌握还是有必要的吧。(比如这一题我也被卡map，最后吸氧过的)
您可能已经不理这个贴了，那就当作我发表一下自己的看法，供后人借鉴吧。
萌新发言，个人见解，大佬轻喷
by Lice @ 2020-05-22 22:28:55
@[_Wallace_](/user/61430) map 版的构造复杂度应该不是 $O(n \log |\Sigma|)$ 吧……
感觉差距在在 SAM 上转移的时候，数组的单次转移是 $O(1)$ 的，map 的单次是 $O(\log |\Sigma|)$ 的？
by 一扶苏一 @ 2020-05-22 22:39:39