当一次成功插入之后,暴力的做法是使 rem−1,并从根向下找到 s[n−rem+1⋯n] 对应的位置继续插入。不难发现这样找到的节点是之前所在节点的后缀链接指向的节点,在正确维护后缀链接之后,我们就可以不需要每次从根向下查找,成功插入之后可以直接跳到后缀链接处,即 now=link[now]
。特别地,如果当前所在节点为 0 ,我们应使 len-=1
。
摘自 炫酷后缀树魔术
我对这段话有疑惑:前半部分说成功插入后一定使 rem-1,但后半部分又说不用,只需要 now=link[now],这是为什么?