有关这件事。

常规写 SAM 的时候空间复杂度是 $O(n|\Sigma|)$ 的。

为了降低空间复杂度，由于 SAM 的转移数量是 $O(n)$ 级别的，所以每个状态开一个 vector 存这个状态的转移。这样把时间复杂度牺牲到 $O(n|\Sigma|)$，但是空间就是 $O(n)$ 了。我算了一下常数也是过得去的。

但是仍然 MLE 了。所以 SAM 到底哪个地方空间比我想象得要大？？？