PAM,求证性质
  • 板块学术版
  • 楼主hsfzLZH1
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/2/14 22:54
  • 上次更新2023/11/5 03:15:57
查看原帖
PAM,求证性质
43486
hsfzLZH1楼主2021/2/14 22:54

设 PAM 上一结点 uuv=fail(u)v=\operatorname{fail}(u) , 令 d(x)=xfail(x)d(x)=|x|-|\operatorname{fail(x)}| ,是否一定有 d(u)d(v)d(u)\ge d(v)

(换句话说,设字符串 s1,s2,s3s_1,s_2,s_3s1s_1 为回文串, s2s_2s1s_1 的不相等且最长的回文后缀, s3s_3s2s_2 的不相等且最长的回文后缀,那么是否一定有 s1s2s2s3|s_1|-|s_2|\ge |s_2|-|s_3| ?)

若是,则从一个结点开始跳 fail\operatorname{fail} 指针,经过结点的 dd 值是否只有 O(logn)O(\log n) 种取值?

这是不是就是什么“回文自动机fail链上分组维护信息加速DP”啊

2021/2/14 22:54
加载中...