下午上台发言的时候有点呆滞，感觉讲的东西自己都听不懂。可能讲课水平不太行。

首先考虑计数所有子串均大于等于s的串的个数。

然后对串s建立KMP自动机，补齐26n条转移边的那种。

注意根据题意，部分跳回根的转移边是不合法的

之后枚举在自动机里走了无穷多个串s之后到达的节点是点u。

由这个定义，在自动机里，从点u出发行走完一个完整的串s之后，会回到点u自己。

于是我们只要解决在一张有向图上，一个点出发走m步回到自己的方案数即可。单次复杂度$O(m * n * 26)$

由于还要枚举点u，所以总的复杂度是$O(n^2m * 26)$

而且可以发现这个算法并不依赖于n与m的大小关系。

这样我们就能获得60分啦。

实际上这个算法是有漏洞的。

一个点每条转移边并不是都能走。

想像一下，串s形如abdabc，我们现在在长度为5的前缀对应的节点上。

如果下一个字符是c，那么在这个无穷循环串中，我们就会获得一个子串abc，显然由此可以导出一个比s小的子串。

所以，每个点上所有不是跳回根的转移边只有字符最大的一条有用。

如果从根出发只走这样的转移边，那么会形成一个rho的形状。

考虑在这个rho上计数。

我们先算出$f_{i,j}$表示从根出发走i步，走到节点j的方案数。这一部分复杂度$O(nm)$。

然后还是跟之前一样枚举节点u。

如果u不经过根，那么路径唯一，方案数可以$O(1)$计算。

如果u经过根，那么枚举从u出发走几步才跳回根。这一部分复杂度也是$O(nm)$。

最后该算法总复杂度为$O(mn)$。

感觉rho的结构挺简洁的吧，不过考场上由于某些原因，并没有考虑过改进复杂度。

有没有老哥来把前面这个算法优化一下啊？

upd:

可能是可以优化的。

设生成函数F满足$f_i$为从根出发走$i$步第一次走回根的方案数。

F是可以直接在KMP过程中计算的。

所有节点走$m$步并且经过根的总方案数应该是$[x^m] (F' * x -F +1) * \frac{1}{1-F}$

复杂度应该是$O(n+mlogm)$。