题目链接

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

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

看到问题后一个自然的想法是求出每个前缀的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中有用。