快速构造后缀自动机

参考资料

我觉得原文中对于为什么要新开一个节点讲得还不是很透彻.
考虑新建一个节点u时, 我们一直往上跳suffix link, 到了(lst)节点. 我们发现(lst)已经有一个出边(c), 因此要进行特殊处理:

假如可以直接将(u)的suffix link设为(p), 则根据suffix link的定义, 有(minlen(u) = len(p) + 1). 又因为(minlen(u) = minlen(x) + 1 = len(lst) + 2)((x)到(u)有连边, 因而(minlen(u) = minlen(x) +1); 又因为(lst)为(x)的suffix link, 因此(minlen(x) = minlen(lst) + 1)), 所以有(len(lst) + 2 = len(p) + 1), 所以有(len(lst) + 1 = len(p))
反之, 假如(len(lst) + 1 < len(p)), 则有(u)的suffix link不为(p), 需要新建一个(len(q) = len(lst) + 1)的节点.