P15725 [JAG 2023 Summer Camp #3] LCP Queries

对于一个字符串 $y$，如果字符串 $x$ 可以通过零次或多次移除 $y$ 的最后一个字母得到，则称 $x$ 是 $y$ 的一个**前缀**。例如，“abac”、“aba”、“ab”、“a” 以及空字符串都是 “abac” 的前缀。 对于两个字符串 $x$ 和 $y$，令 $\text{LCP}(x, y)$ 表示 $x$ 和 $y$ 的最长公共前缀的长度。例如，$\text{LCP}(\text{“abacab”}, \text{“abacbba”}) = 4$，因为这两个字符串的最长公共前缀是 “abac”。注意，对于任意字符串 $x$ 和 $y$，$\text{LCP}(x, y)$ 总是有定义的，因为至少空字符串是它们的公共前缀之一。 给定 $n$ 个小写英文字母串 $s_1, \ldots, s_n$ 和 $m$ 个小写英文字母串 $t_1, \ldots, t_m$。接下来，给定 $q$ 次查询。每次查询给定一个整数序列 $a_1, \ldots, a_k$。令 $u$ 为 $t_{a_1}, \ldots, t_{a_k}$ 的连接。你的任务是计算 $\sum_{i=1}^{n} \text{LCP}(u, s_i)$。

输入包含一个单独的测试用例，格式如下： $$ \begin{aligned} &n \\ &s_1 \\ &\vdots \\ &s_n \\ &m \\ &t_1 \\ &\vdots \\ &t_m \\ &q \\ &\text{Query}_1 \\ &\vdots \\ &\text{Query}_q \end{aligned} $$ 第一行包含一个整数 $n$。接下来的 $n$ 行，每行包含一个非空的小写英文字母串 $s_i$。接下来一行包含一个整数 $m$。接下来的 $m$ 行，每行包含一个非空的小写英文字母串 $t_j$。 接下来一行包含一个整数 $q$。随后按顺序给出 $q$ 次查询。每次查询以单独一行的形式给出，格式如下： $$ k \ a_1 \ \ldots \ a_k $$ 其中 $k$ 是一个正整数，表示本次查询的整数序列的长度。每个 $a_i$ 是一个介于 $1$ 到 $m$ 之间（含）的整数。 可以假设 $1 \leq n \leq 200,000$，$1 \leq m \leq 200,000$ 且 $1 \leq q \leq 200,000$。所有 $s_i$ 的长度之和不超过 $200,000$。类似地，所有 $t_i$ 的长度之和不超过 $200,000$。所有查询的 $k$ 值之和不超过 $200,000$。

输出 $q$ 行。第 $i$ 行应为第 $i$ 次查询的答案。

翻译由 DeepSeek V3.2 完成