萌新学后缀树学哭了
  • 板块学术版
  • 楼主Mister5
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/5/11 21:01
  • 上次更新2023/11/7 02:38:19
查看原帖
萌新学后缀树学哭了
321218
Mister5楼主2020/5/11 21:01

当一次成功插入之后,暴力的做法是使 rem1rem-1,并从根向下找到 s[nrem+1n]s[n-rem+1 \cdots n] 对应的位置继续插入。不难发现这样找到的节点是之前所在节点的后缀链接指向的节点,在正确维护后缀链接之后,我们就可以不需要每次从根向下查找,成功插入之后可以直接跳到后缀链接处,即 now=link[now] 。特别地,如果当前所在节点为 00 ,我们应使 len-=1

摘自 炫酷后缀树魔术

我对这段话有疑惑:前半部分说成功插入后一定使 rem-1,但后半部分又说不用,只需要 now=link[now],这是为什么?

2020/5/11 21:01
加载中...