[CF744E] Hongcow Masters the Cyclic Shift

给定一个字符串集合 $S$，若由 $S$ 中 $k$ 个可相同的字符串拼接而成的字符串 $s$ 恰有 $k$ 个循环移位能由若干 $S$ 中的字符串拼成，则称其为好的。一个集合 $S$ 为好的，当且仅当所有能由 $S$ 中若干可相同的字符串拼接而成的字符串都是好的。给定字符串序列求有多少区间中的字符串集合是好的。

如果一个集合是好的，显然一个集合的所有子集都是好的，所以序列中的任意两个极长区间一定互不包含，可以双指针转化成做 $O(n)$ 次检查某个字符串集合 $S$ 是否是好的（注意这里需要去重）。

我们将“若干字符串拼接后得到两个互为循环移位的字符串 $s_1,s_2$”这个过程用一个图来表示：对集合 $S$ 中的每个字符串的每个非空后缀 $t$ 建两个状态分别表示 $s_1=s_2t$，和 $s_2=s_1t$；建空状态表示 $s_1=s_2$。

对字符串做 z-algorithm，可以 $O((\sum_{x\in S}|x|)^2)$ 地连边。途中有环则说明改集合不合法。

更进一步地，如果某个表示 $s_1=s_2t$ 的状态 $t$ 能够到达表示 $s_2=s_1t$ 的状态，根据对称性，它一定能到达它自己。所以对称的两个状态要么在同一个强连通分量里，要么互不能到达。据此我们可以给每个非空后缀只建一个点。