Description：

给定一个字符串，求有多少个本质不同的可以覆盖这整个串，允许重复覆盖也允许在头部和尾部进行不完全的覆盖的子串，输出这样的子串个数以及长度最小的合法子串，如果有多个合法的串输出字典序最小的那个。

$1\leqslant n\leqslant 200000$

Solution：

首先先建出 $SAM$ ，然后我们可以用线段树维护 $Right$ 集合，在 $parent$ 树上线段树合并可以求出某个节点的 $Right$ 集合，然后我们就可以顺便维护出这个点的 $Right$ 集合的两个位置之差的最小值 $mx$ ，那么这个点所代表的串的取值范围就是 $[\max(s[s[p].par].maxl+1,mx),s[p].maxl]$ ，但是我们会发现这样不能处理串的开头和结尾的情况，那么我们就需要特殊处理，对于开头，情况应该是第一个多出去一些，然后第一个和第二个有一些交叉，那么我们会发现如果这个字符串第一次出现的位置是 $[l,r]$ ，那么 $nxt[r]\geqslant l-1$ ，意思就是说必须都盖住，那么我们先 $KMP$ 求出 $nxt$ 数组，我们把这个串翻转过来建立后缀自动机，对于后缀自动机上的每个点分别计算合法的子串个数考虑后缀自动机上的一个点，我们可以知道它第一次出现的位置 $p$ ，设这个字符串长度的区间为 $[l,r]$ ，那么我们就要统计 $[p+l-1,p+r-1]$ 中 $nxt[i]\geqslant l-1$ 的位置 $i$ ，这个可以用主席树二维数点来解决，这个时候发现我们只要知道这个串的长度的取值范围就可以统计了。然后我们再处理结尾，发现结尾不算多出去的那些是这个串的一个前缀，也就是后缀树上（反串后缀自动机 $par$ 树上）的一个祖先，那么我们实际上就是要求是否有一个祖先它存在一个串刚好能放到字符串最后，显然这个长度越大越好，因为越大越有可能在 $par$ 树他的子树中符合条件，然后我们沿着 $par$ 树从上往下递推这个最大值，如果能更新就把最大值更新，显然比这个值长度大而且还能和前面的接上的都是可以覆盖最后的，这样我们就得到了这样的子串个数。

对于字典序最小的解，可以用一个数据结构维护 $nxt$ 然后再查询的时候找一个最靠前的，相同长度的可以用二公分 $+$ 哈希或者后缀数组判。

Code：

代码就懒得写了