题目链接
很久以前我想过这个问题，但当时没有什么好的办法。
昨天去做了下江苏省选二轮的题，发现居然被出出来了。
看到问题后一个自然的想法是求出每个前缀的lyndon word分解（模板题在此）。
但是博主只知道Duval算法（可以看鏼爷论文），然后该算法需要在字符串结尾补字符，如果要求出每个前缀的lyndon word分解，原来的均摊分析就失效了。
回忆一下Duval算法的过程，前缀做完之后是（若干已经做好的）+（某个串s）重复t遍+s的某个前缀u。
可以证明，已经做好的部分对答案没有影响，（某个串s）重复t遍对答案有影响的部分只有第一次出现的位置，而整个串都可能对答案有影响。
怎么办？
一个想法是，那就同时维护出串，在执行Duval算法后的状态。
但是串执行完Duval算法后会得到一个串u'，我们需要递归执行前述的过程。
容易发现，所以这个“递归”只会有 层。
具体实现可以参考这份代码
让我们思考一些可能的优化。
首先一个想法是，在Duval算法运行过程中，既然串在之前已经出现过了，那么是不是可以复用之前的运算结果？
记串u第一次出现的位置的结尾处为
也就是说，我们猜想，注意这里的可以认为是-题目要求输出的真实的答案。
如果这样不对，那么必然存在两个位置和使得前缀从开始和从开始的循环移位都是相等的。
否则这两个位置开始的循环移位在之前已经比出大小，从扩展到不会对大小比较产生影响。
从而前缀构成的串存在非平凡整循环节。
同理可以证明也存在非平凡整循环节.
如此递归下去，可以得到串字符全部相等，此时我们可以平凡地验证结论的正确性。
有了这个结论，配合线性SA和RMQ，我们可以获得本题的一个线性算法。
不过线性SA和RMQ太难写了，博主写不动。
由于lyndon word的性质和Duval算法的正确性，在处理前缀的答案时，所对应的后缀必然大于等于串s的等长前缀。
所以我们只需使用字符串哈希判定子串相等，之后便转化为了一个子串和原串比较大小，这可以通过exkmp来线性实现。
最后提交在这里，好像比还慢。
如果本文论述出现了漏洞，欢迎读者指出。
PS: 听说16年有篇论文提出了关于子串最小循环的算法，感觉本文可能只在OI中有用。
