同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21644_Subsequence

2022-5-16 18:20| 发布者: Hocassian| 查看: 31| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505716049100-Problem List-采集的数据-后羿采集器.html

Pro.ID

21644

Title

Subsequence

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21644

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

We say that a string A is a subsequence of another string B, if there is a number sequence C which satisfies the following conditions:

C has exactly length(A) numbers;
0 ≤ C[0] < C[1] < ... < C[length(A)-1 ] < length(B);
A[i] = B[C[i]] for each number i ( 0 ≤ i < length(A) ).

For example, "abed" is a subsequence of "aaaaaabbbed", while "abed" is not a subsequence of "aaaaacccdb". Of course any string is a subsequence of itself.

In this problem, you are given a long string A, and many short strings B_i. You need to write a fast program which tells whether B_i is a subsequence of A.

输入

On the first line of input, there is a positive integer T ≤ 20 specifying the number of test cases follow.

The first line of each test case gives the string A. The second line contains an integer M ( 0 < M ≤ 10000 ), which is the number of short strings B_i. And the next following M lines each contain a string B_i.

The length of A will be no more than 100,000 and the length of all B_i will be no more than 50. All the strings will have at least one letter, and all the letters will appear in lowercase.

输出

Description

We say that a string A is a subsequence of another string B, if there is a number sequence C which satisfies the following conditions:

C has exactly length(A) numbers;
0 ≤ C[0] < C[1] < ... < C[length(A)-1 ] < length(B);
A[i] = B[C[i]] for each number i ( 0 ≤ i < length(A) ).

For example, "abed" is a subsequence of "aaaaaabbbed", while "abed" is not a subsequence of "aaaaacccdb". Of course any string is a subsequence of itself.

In this problem, you are given a long string A, and many short strings B_i. You need to write a fast program which tells whether B_i is a subsequence of A.

Input

On the first line of input, there is a positive integer T ≤ 20 specifying the number of test cases follow.

The length of A will be no more than 100,000 and the length of all B_i will be no more than 50. All the strings will have at least one letter, and all the letters will appear in lowercase.

Output

The output of each test case contains M+1 lines. The first line should be "Case X:" (quotes for clarity) where X is the number of the test case (starting at 1).

Then M lines follow: for each Bi , if it's a subsequence of A output "Yes", otherwise output "No".

Sample Input

2
subsequence
2
sequence
bus
problem
1
rom

Sample Output

Case 1:
Yes
No
Case 2:
Yes

Source

ZS 2009 pre