UOJ Logo zx2003的博客

博客

关于 [JSOI2019]节日庆典 的一个线性做法

2019-06-01 20:48:08 By zx2003

题目链接

很久以前我想过这个问题,但当时没有什么好的办法。

昨天去做了下江苏省选二轮的题,发现居然被出出来了。

看到问题后一个自然的想法是求出每个前缀的lyndon word分解(模板题在此)。

但是博主只知道Duval算法(可以看鏼爷论文),然后该算法需要在字符串结尾补$ - \infty $字符,如果要求出每个前缀的lyndon word分解,原来的均摊分析就失效了。

回忆一下Duval算法的过程,前缀$i$做完之后是(若干已经做好的)+(某个串s)重复t遍+s的某个前缀u。

可以证明,已经做好的部分对答案没有影响,(某个串s)重复t遍对答案有影响的部分只有第一次出现的位置,而$u$整个串都可能对答案有影响。

怎么办?

一个想法是,那就同时维护出串$u$,在执行Duval算法后的状态。

但是串$u$执行完Duval算法后会得到一个串u',我们需要递归执行前述的过程。

容易发现$|u| \le |s| \le \frac{i}{2}$,所以这个“递归”只会有 $logn$ 层。

具体实现可以参考这份代码

让我们思考一些可能的优化。

首先一个想法是,在Duval算法运行过程中,既然串$u$在之前已经出现过了,那么是不是可以复用之前的运算结果?

记串u第一次出现的位置的结尾处为$x$

也就是说,我们猜想$ans_i=min(串s第一次出现的位置的开头,ans_x)$,注意这里的$ans_i$可以认为是$i$-题目要求输出的真实的答案。

如果这样不对,那么必然存在两个位置$p$和$q$使得前缀$x$从$p$开始和从$q$开始的循环移位都是相等的。

否则这两个位置开始的循环移位在$x$之前已经比出大小,从$x$扩展到$i$不会对大小比较产生影响。

从而前缀$x$构成的串存在非平凡整循环节$y$。

同理可以证明$y$也存在非平凡整循环节.

如此递归下去,可以得到串$x$字符全部相等,此时我们可以平凡地验证结论的正确性。

有了这个结论,配合线性SA和$O(n)-O(1)$RMQ,我们可以获得本题的一个线性算法。

不过线性SA和$O(n)-O(1)$RMQ太难写了,博主写不动。

由于lyndon word的性质和Duval算法的正确性,在处理前缀$i$的答案时,$ans_x$所对应的后缀必然大于等于串s的等长前缀。

所以我们只需使用字符串哈希判定子串相等,之后便转化为了一个子串和原串比较大小,这可以通过exkmp来线性实现。

最后提交在这里,好像比$O(nlogn)$还慢。

如果本文论述出现了漏洞,欢迎读者指出。

PS: 听说16年有篇论文提出了关于子串最小循环的$O(n)-O(1)$算法,感觉本文可能只在OI中有用。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。