题解：P10646 [NordicOI 2023] ChatNOI

很妙的题。

每次加入一个字符串可以看作是一种转移，可以把这个过程抽象成一个图论问题。那么就可以把 $k$ 个连续的单词看作是一个点，对于每个连续 $k+1$ 的单词，从前 $k$ 个单词的点连一条到后 $k$ 个单词所代表的点的边，边权是这个长度为 $k+1$ 的连续段的出现次数。

由于每个长度为 $k+1$ 的连续段对应着唯一的一条边，所以边权总和是不超过 $n$ 的，容易证明边权种类数至多是 $\mathcal O(\sqrt n)$ 的。

这样子假设最终答案的字符串组质量为 $x$，那么相当于从起点开始走 $m$ 步，每次经过的边权必须不小于 $x$。

那么我们可以把询问离线下来，从大到小枚举边权的种类，把边从大到小加入，然后建反图跑拓扑排序，求出每个点开始的最长路，然后更新答案即可。如果从某个点开始能经过环，那么从这个点开始就可以无限走。

由于边权种类至多是 $\mathcal O(\sqrt n)$ 的，所以上述做法是 $\mathcal O(\sqrt n(n+q))$ 的，实际上跑不满，很容易通过。