CVBB ACM Team

这个题要是从runs是什么以及怎么求开始讲那得到下辈子讲完了，就捞干的说点结论。

首先，runs是一个三元组构成的集合，其中 $(l,r,p)$ 表示 $S[l,r]$ 的最小周期是 $p$ ，且 $S[l-1]!=S[l-1+p]$ 且 $S[r+1]!=S[r+1-p]$ ，同时 $r-l+1 \ge 2p$。这里有一些比较神秘的点，就是这个周期不一定是整周期，只需要一直满足 $S[i]=S[i+p]$ 即可。

然后，我们定义了一个叫 Lyndon根 的东西。这玩意是说，在每个三元组中，找到其一个长度是 $p$ 的子串，在给定偏序关系下是 Lyndon串，那么这玩意就是它的 Lyndon根。之后我们考虑求出来每个位置向后的最长的 Lyndon串，由于每个三元组的 Lyndon根 必然形如 $S[i,ly(i)]$ ，那么我们就可以通过求出来之后向两侧扩展来得到这个三元组了。

每个平方串都会在一个三元组中，那么我们就可以通过在每个三元组中枚举平方串的方式来得到我们所有可能的平方串了。这样我们的枚举次数是 $\sum{(r-l+1)/2p*p}=\sum{(r-l+1)/2}$ 的。