P12962 [GCJ Farewell Round #4] Genetic Sequences

Margaret 正在研究基因序列。她正在分析一种新型生命体的两个序列 $\mathbf{A}$ 和 $\mathbf{B}$，这种生命体不使用典型的四字母遗传密码。基因序列的编码方便地使用了 26 个大写英文字母 'A' 到 'Z' 来表示。 Margaret 想要比较序列 $\mathbf{A}$ 和 $\mathbf{B}$。最佳方法是进行一系列序列分析测试。每个测试需要从 $\mathbf{A}$ 中取出一个前缀（称为 $\mathbf{A}$-前缀），包含 $\mathbf{A}$ 的前 $\mathbf{P}$ 个字母；同时从 $\mathbf{B}$ 中取出一个后缀（称为 $\mathbf{B}$-后缀），包含 $\mathbf{B}$ 的最后 $\mathbf{S}$ 个字母。然后 Margaret 需要比较 $\mathbf{A}$-前缀和 $\mathbf{B}$-后缀。子串是指连续的字母子序列。如果 $\mathbf{B}$-后缀以某个 $\mathbf{A}$-前缀的子串开头，即该子串是 $\mathbf{B}$-后缀的前缀，则称该子串与 $\mathbf{B}$-后缀匹配。测试的结果是 $\mathbf{A}$-前缀中能与 $\mathbf{B}$-后缀匹配的最长子串的长度。 Margaret 需要一些软件来确定一批 $\mathbf{Q}$ 个序列分析测试的结果。注意每个测试都是独立的。Margaret 有 $\mathbf{A}$ 和 $\mathbf{B}$ 的多个副本，每个测试都使用新的副本。

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个字符串和一个整数，分别是 $\mathbf{A}$、$\mathbf{B}$ 和 $\mathbf{Q}$。每个测试用例的最后是 $\mathbf{Q}$ 行，第 $i$ 行包含两个整数 $\mathbf{P}_i$ 和 $\mathbf{S}_i$，表示第 $i$ 个序列分析测试的前缀和后缀大小。

对于每个测试用例，输出一行 `Case #x: y1 y2 ... yQ`，其中 $x$ 是测试用例编号（从 1 开始），$y_i$ 是第 $i$ 个查询的答案。

**样例解释** 在样例 #1 中，有 3 个测试。第一个测试比较 $\mathbf{A}$ 的前缀 $\mathbf{A B C}$ 和 $\mathbf{B}$ 的完整后缀 $\mathbf{C A B A B A}$。答案是 1，因为 $\mathbf{C}$ 是 $\mathbf{A B C}$ 中包含的最长子串，且是 $\mathbf{C A B A B A}$ 的前缀。第二个测试比较 $\mathbf{A B C A B A C}$ 和 $\mathbf{C A B A B A}$，最长匹配是 $\mathbf{C A B A}$。第三个测试比较 $\mathbf{A B C A B A}$ 和 $\mathbf{A B A B A}$，最长匹配是 $\mathbf{A B A}$。 在样例 #2 中，有 2 个测试。第一个测试比较 $\mathbf{B A N A N}$ 和 $\mathbf{B A N A}$，最长匹配是 $\mathbf{B A N A}$。第二个测试比较 $\mathbf{B A N A N}$ 和 $\mathbf{A B A N A}$，最长匹配是 $\mathbf{A}$。 在样例 #3 中，有一个测试。比较 $\mathbf{A B}$ 和 $\mathbf{D}$。由于没有匹配，答案是 0。 **限制** - $1 \leq \mathbf{T} \leq 100$。 - $1 \leq \mathbf{P}_i \leq \mathbf{A}$ 的长度。 - $1 \leq \mathbf{S}_i \leq \mathbf{B}$ 的长度。 **测试集 1（5 分，可见评测结果）** - $1 \leq \mathbf{A}$ 的长度 $\leq 3000$。 - $1 \leq \mathbf{B}$ 的长度 $\leq 3000$。 - $1 \leq \mathbf{Q} \leq 3000$。 **测试集 2（17 分，隐藏评测结果）** - $1 \leq \mathbf{A}$ 的长度 $\leq 10^5$。 - $1 \leq \mathbf{B}$ 的长度 $\leq 10^5$。 - 所有测试用例中 $\mathbf{A}$ 的长度总和 $\leq 5 \times 10^5$。 - 所有测试用例中 $\mathbf{B}$ 的长度总和 $\leq 5 \times 10^5$。 - $1 \leq \mathbf{Q} \leq 10^5$。 翻译由 DeepSeek V3 完成