P5404

题目链接 观察题目，我们发现直接计算是困难的，先构造单个合法的 \(T\) 分析其性质。 为了构造出 \(T\)，先考虑构造时 \(T\) 时什么时候会出现不合法的情况，此时 \(T\) 会有一段和 \(S\) 相同的前缀，且这段前缀后面跟着的字符比 \(S\) 所跟的小。 为了避免这种情况出现，我 ......

考虑拿总方案数减去不合法方案数。一个字符串不合法当且仅当其所有长度为 $|s|$ 的子串字典序都 $\ge |s|$。把这个东西用 KMP 自动机的角度来理解就是假设当前在 KMP 自动机的节点 $x$，那么下一步你匹配的字符必须 $\ge$ $x$ fail 树上所有祖先节点对应的下一个字符的最大 ......