P9778 [HUSTFC 2023] 基因编辑

RegisterFault · 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|)。