如何证明 Suffix Automaton (后缀自动机) 的时空复杂度?

Question

写了一篇 SAM 的教程, 但是不知道该怎么证明时间复杂度, 具体见 Suffix Automaton Tutorial 的 SAM: The Time/Space Complexity 小节的描述:

接着我们来考虑 time complexity. 根据 SAM 的构建算法, 影响 time complexity 的操作有三种:

1. 第 (2) 步的创建 transitions.

2. 第 (5) 步的 copy transitions from q to sq.

3. 第 (5) 步的重定向 transitions ChildrenTrans.

显然, (1) 与 (2) 只涉及创建新的 transition, 由于 transition 的上限是 O(n), 所以均摊后 (1) 与 (2) 类操作的复杂度是 O(n). 至于 (3) 我就不知道怎么证了, 我找到了一些 paper 说这个是可以证的, 但是具体怎么搞我没想清楚. 如果你有比较好的证明方法, 请务必告诉我, 我请你喝咖啡!