众所周知 SAM 状态数和操作次数都是线性的，时空复杂度的瓶颈在对于状态查找字符是 c 的出边上。

所以有这样一个问题，总值域大小是 $|\Sigma|$ 的，有 $\Theta(n)$ 次操作：

1. 给定 $x'$ 求这个键在结点 $u$ 上是否存在，如果存在返回这个键对应的值。

2. 在结点 $u$ 上插入一个键值对 $(x,\,y)$，保证每次插入的键不同。

在 $|\Sigma| = 26$，$|\Sigma| = 128$ 和 $|\Sigma| = \Theta(n)$ 时分别有什么优秀的解法吗。