关于PAM中的回文子串划分
  • 板块灌水区
  • 楼主crimson000
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/4 19:58
  • 上次更新2023/11/3 05:53:24
查看原帖
关于PAM中的回文子串划分
755337
crimson000楼主2023/8/4 19:58

学术版没人回只能发灌水区了

这里先把OIwiki中的图放上来:

这个图我的理解是把下面橙色的部分向左平移了 diff[x]diff[x] 得到了上面的蓝色部分,其中蓝色节点 f 的和为 g[fail[x]]g[fail[x]],这样的话 g[x]g[x] 和 g[fail[x]]g[fail[x]] 相差的部分就是下面橙色的最长那一条,也就是用 f[i−len[x]]f[i-len[x]] 来更新 g[x]g[x]。但是 OIwiki 和题解区给出的都是用 f[i−diff[x]−len[slink[x]]]f[i-diff[x]-len[slink[x]]],即橙色部分中最短的那一部分来更新。

一直没搞懂这里为什么这么更新,或者是我上面的话中有哪里弄错了导致得出的这个错误结论,又或者是我对这张图的理解有误,求大佬指出(解答),轻喷

2023/8/4 19:58
加载中...