问题引入 如果我们需要一种算法，使其可以将一个字符串的所有子序列表示为一个 DAG（即有向无环图），我们该如何构建？ 构建 钦定 $n$ 为字符串的长度，$\Sigma$ 为字符集，$S$ 为字符串，且 $S$ 只会包含小写字母。 我们定义 $nxt_ (i \leq ...

3578 字 丨 11.9分钟

问题引入 假如我们要用一个有向无环图存一个字符串的所有子串，然后跑各种图论中的算法，以 $abaab$ 为例，该怎么做 SAM介绍 注意到，这种方法的时间在最劣的情况下是 $O(n^2)$ 的，因为其中还有很多部分可以优化 观察到 $a→a→b...

8978 字 丨 29.9分钟