关于一些细节
查看原帖
关于一些细节
857014
_Communist楼主2025/2/6 21:20

这篇题解所说的方法为前提。

  1. 第二段中 “预处理 tt 的后缀排序即可比较 tt 的两个后缀的字典序大小”这句话应该是存在一些问题的。假如从当前位到结尾字典序都没有分出大小,后缀排序默认超出下标的部分是空,但我们知道这道题在 tt 之后还有一个部分是 sj+1,ns_{j+1,n},后缀排序会忽略掉这个部分。hack:

in:

10 1
0000110011
1100110011

out:

8

但是该题解输出 10。问题在于虽然以 11 开头的后缀(空)的字典序小于以 9 开头的后缀 11 字典序,但是两个方案形成的最终串字典序是反过来的,就是没有考虑 sj+1,ns_{j+1,n} 的部分。

  1. 第三段中“最小循环节”哈希相同只是一个必要条件,如果往前移的过程中改变了方案的最终串也是不能移动的。hack 这里有
2025/2/6 21:20
加载中...