自动搬运

查看原文

来自洛谷，原作者为

	RegisterFault **

搬运于2025-08-24 22:51:46，当前版本为作者最后更新于2023-11-17 22:04:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没有题解，我来嘴巴一个。

首先考虑枚举被拼出的字符串 $s_k$，然后枚举分界点 $p$。$s_{[1 \sim p]}$ 是一个串的前缀，$s_{[p + 1 \sim |s|]}$ 是一个串的后缀。统计前缀为 $s_{[1 \sim p]}$ 的方案和后缀为 $s_{[p + 1 \sim |s|]}$ 的方案乘积。由于 $\sum |S| \le 2 \times 10 ^ 6$，所以枚举这部分复杂度是 $O(\sum |S|)$。

然后考虑计算方案。可以将每个字符串前缀插到一个前缀 trie 里，后缀插到一个后缀 trie 里。每个单词结尾打上标记。然后变成了子树求和问题。这是容易的。

因此时间复杂度 $O(\sum |S|)$。