社区讨论

PAM,求证性质

学术版参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@locmd9pz
此快照首次捕获于
2023/10/30 16:09
2 年前
此快照最后确认于
2023/11/05 03:15
2 年前
查看原帖
设 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”啊

回复

3 条回复,欢迎继续交流。

正在加载回复...