关于lyndon & Runs
  • 板块学术版
  • 楼主Youth518
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/2/16 09:36
  • 上次更新2023/11/5 03:13:21
查看原帖
关于lyndon & Runs
201158
Youth518楼主2021/2/16 09:36

萌新刚学runs,我想问一下看见了一个定理,理解上有一点疑问


对于 r=(l,r,s) 是串 s 的一个 run ,有且仅有一种 f \in {0,1},满足 s[r+1] <f<_f s[r+1-p],此时 r 所有在 <f<_f 下的lyndon root λ\lambda = s [iλ,jλi_{\lambda},j_{\lambda}] 都与 lyndon array(iλi_{\lambda}) 相等


我想问一下,在另一种字典序下的 lyndon root 的开头位置的 lyndon array 不是也等价于 lyndon root 本身吗,我觉得是不是可以理解为 <f<_f 的情况下一定成立,但是在另一种字典序下可能成立,因为在另一种字典序下可能存在某种情况就是某一个 lyndon array 向右延伸至了 r+1 的位置,此时由于 s[r+1]>s[r+1-p] 所以形成的新串仍是一个 lyndon word,不满足上述条件

2021/2/16 09:36
加载中...