#P12962. [GCJ Farewell Round #4] Genetic Sequences

    ID: 12764 Type: RemoteJudge 20000ms 2048MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>2023后缀自动机 SAMST 表后缀数组 SAGoogle Code Jam

[GCJ Farewell Round #4] Genetic Sequences

题目描述

Margaret researches genetic sequences. She is analysing two sequences A\mathbf{A} and B\mathbf{B} from a new kind of life that does not use the typical four letter genetic alphabet. The code for the genetic sequences conveniently requires 26 letters represented by the uppercase English letters 'A' through 'Z'.

Margaret wants to compare the sequences A\mathbf{A} and B\mathbf{B}. The best way to do this is to do a series of sequence analysis tests. Each test involves taking a prefix from A\mathbf{A} containing only the first P\mathbf{P} letters from A\mathbf{A}, which is called the A\mathbf{A}-prefix. Each test also involves taking a suffix from B\mathbf{B} containing only the last S\mathbf{S} letters from B\mathbf{B}, which is called the B\mathbf{B}-suffix. Margaret then needs to compare the A\mathbf{A}-prefix to the B\mathbf{B}-suffix. A substring is a subsequence of contiguous letters. A substring from the A\mathbf{A}-prefix matches the B\mathbf{B}-suffix if the B\mathbf{B}-suffix starts with that substring. That is, the substring is a prefix of the B\mathbf{B}-suffix. The result of a test is the length of the longest substring from the A\mathbf{A}-prefix that matches the B\mathbf{B}-suffix.

Margaret needs some software to determine the outcome of a batch of Q\mathbf{Q} sequence analysis tests. Note that each test is independent. Margaret has many copies of A\mathbf{A} and B\mathbf{B} and a new one is used for each test.

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow. Each test case begins with a line containing two strings and an integer, A\mathbf{A}, B\mathbf{B}, and Q\mathbf{Q} respectively. Each test case ends with Q\mathbf{Q} lines, the ii-th of which contains two integers Pi\mathbf{P}_i and Si\mathbf{S}_i, which are the prefix and suffix sizes for the ii-th sequence analysis test.

输出格式

For each test case, output one line containing Case #xx: y1y_1 y2y_2 \ldots yQy_{\mathbf{Q}}, where xx is the test case number (starting from 1) and yiy_i is the answer to the ii-th query in the input.

3
ABCABAC CABABA 3
3 6
7 6
6 5
BANANA HABANA 2
5 4
5 5
ABC ABD 1
2 1
Case #1: 1 4 3
Case #2: 4 1
Case #3: 0

提示

Sample Explanation

In Sample Case #1, there are 3 tests. The prefix ABC\mathbf{A B C} from A\mathbf{A} and the complete suffix CABABA\mathbf{C A B A B A} from B\mathbf{B} are compared in the first test. The answer is 1, since c\mathbf{c} is the longest substring that is contained in ABC\mathbf{A B C} and is a prefix of CABABA\mathbf{C A B A B A}. In the second test, ABCABAC\mathbf{A B C A B A C} is tested against CABABA\mathbf{C A B A B A} and the longest match is CABA\mathbf{C A B A}. In the third test, ABCABA\mathbf{A B C A B A} is tested against ABABA\mathbf{A B A B A} and the longest match is ABA\mathbf{A B A}.

In Sample Case #2, there are 2 tests. In the first, BANAN\mathbf{B A N A N} is tested against BANA\mathbf{B A N A}, and the longest match is BANA\mathbf{B A N A}. In the second, BANAN\mathbf{B A N A N} is tested against ABANA\mathbf{A B A N A}, and the longest match is A\mathbf{A}.

In Sample Case #3, there is one test. In it, AB\mathbf{A B} is tested against d\mathbf{d}. Since there is no match the answer is 0.

Limits

  • 1T1001 \leq \mathbf{T} \leq 100.
  • 1Pi1 \leq \mathbf{P}_{i} \leq the length of A\mathbf{A}.
  • 1Si1 \leq \mathbf{S}_{i} \leq the length of B\mathbf{B}.

Test Set 1 (5 Pts, Visible Verdict)

  • 11 \leq the length of A3000\mathbf{A} \leq 3000.
  • 11 \leq the length of B3000\mathbf{B} \leq 3000.
  • 1Q30001 \leq \mathbf{Q} \leq 3000.

Test Set 2 (17 Pts, Hidden Verdict)

  • 11 \leq the length of A105\mathbf{A} \leq 10^{5}.
  • 11 \leq the length of B105\mathbf{B} \leq 10^{5}.
  • The sum of the lengths of A\mathbf{A} over all test cases is 5×105\leq 5 \times 10^{5}
  • The sum of the lengths of B\mathbf{B} over all test cases is 5×105\leq 5 \times 10^{5}
  • 1Q1051 \leq \mathbf{Q} \leq 10^{5}.