#P12962. [GCJ Farewell Round #4] Genetic Sequences
[GCJ Farewell Round #4] Genetic Sequences
题目描述
Margaret researches genetic sequences. She is analysing two sequences and 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 and . The best way to do this is to do a series of sequence analysis tests. Each test involves taking a prefix from containing only the first letters from , which is called the -prefix. Each test also involves taking a suffix from containing only the last letters from , which is called the -suffix. Margaret then needs to compare the -prefix to the -suffix. A substring is a subsequence of contiguous letters. A substring from the -prefix matches the -suffix if the -suffix starts with that substring. That is, the substring is a prefix of the -suffix. The result of a test is the length of the longest substring from the -prefix that matches the -suffix.
Margaret needs some software to determine the outcome of a batch of sequence analysis tests. Note that each test is independent. Margaret has many copies of and and a new one is used for each test.
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing two strings and an integer, , , and respectively. Each test case ends with lines, the -th of which contains two integers and , which are the prefix and suffix sizes for the -th sequence analysis test.
输出格式
For each test case, output one line containing Case #: , where is the test case number (starting from 1) and is the answer to the -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 from and the complete suffix from are compared in the first test. The answer is 1, since is the longest substring that is contained in and is a prefix of . In the second test, is tested against and the longest match is . In the third test, is tested against and the longest match is .
In Sample Case #2, there are 2 tests. In the first, is tested against , and the longest match is . In the second, is tested against , and the longest match is .
In Sample Case #3, there is one test. In it, is tested against . Since there is no match the answer is 0.
Limits
- .
- the length of .
- the length of .
Test Set 1 (5 Pts, Visible Verdict)
- the length of .
- the length of .
- .
Test Set 2 (17 Pts, Hidden Verdict)
- the length of .
- the length of .
- The sum of the lengths of over all test cases is
- The sum of the lengths of over all test cases is
- .