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

设 PAM 上一结点 uu , v=fail⁡(u)v=\operatorname{fail}(u) , 令 d(x)=∣x∣−∣fail(x)⁡∣d(x)=|x|-|\operatorname{fail(x)}| ,是否一定有 d(u)≥d(v)d(u)\ge d(v) ?

(换句话说,设字符串 s1,s2,s3s_1,s_2,s_3 , s1s_1 为回文串, s2s_2 为 s1s_1 的不相等且最长的回文后缀, s3s_3 为 s2s_2 的不相等且最长的回文后缀,那么是否一定有 ∣s1∣−∣s2∣≥∣s2∣−∣s3∣|s_1|-|s_2|\ge |s_2|-|s_3| ?)

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

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

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