SUBSN - Subsequence


A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example “abd” is a subsequence of “abcdef”. - Wikipedia.

Your task in this problem is to decide if a given string is a subsequence of another string or not?

Easy?

Input

The first line of input will be the number of test cases. Each test case will start with a line contains a string S, S will have letters from 'a' to 'z' and the length of S ≤ 100,000. This line will be followed by a number Q which is the number of queries you have to answer for the given string S, 1 ≤ Q ≤ 1000. Each of the next Q lines will contain a string T, T will have letter from 'a' to 'z' and the length of T ≤ 200. For each T you have to decide if T is a subsequence of S or not.

Output

For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines will have either “YES” or “NO” if the cross-ponding T is a subsequence of S or not respectively.

Example

Input:
1
abcdef
3
abd
adb
af

Output:
Case 1:
YES
NO
YES

Editors note:
Strings in the input can be empty. Read data carefully to avoid issues. There should be no extra whitespaces of course except '\n'.


hide comments
Xsquare: 2013-05-15 18:24:30

Anyone please suggest a right way to take input?.. I have spent a long time taking right input.. the question is based totally on the input!

nitish rao: 2013-05-15 07:12:46

thank you.. Federico Lebrón :) :)

Last edit: 2013-05-15 07:57:49
Federico Lebrón: 2013-05-15 02:15:08

Ugh. This is an absolutely _dreadful_ input format.

Problem setter, please clarify that both S and T can be absent. That is, empty lines. You should have been clear about this from the beginning - I'm sure the algorithms people were trying were correct, it's the input format that is a mess.

As clarification, the following are valid test cases apparently:

2

2

x
potato
3

p

(Note an empty line after the last "p".)

The output for this test case should be
Case 1:
YES
NO
Case 2:
YES
YES
YES

hossamyosef: 2013-05-15 00:35:31

this problem had been solved by many teams at our contest , please read problem statement well , and try to solve it again :)

Federico Lebrón: 2013-05-14 15:32:37

Um. When you say that T <= 200... you also mean 1 <= T, correct? That is, there are no empty queries. There is also no trailing whitespace (tabs, spaces, newlines, carriage returns?) before or after the string or needles, correct?

Those are the only ways in which I can make my program segfault like this.

I've tried using cin, scanf("%s"), and scanf("%s\n"), to no avail.

Xsquare: 2013-05-14 13:24:39

In full agreement with you both, Jacob Plachta and Federico Lebron!
Either input file should be fixed, or problem should be hidden!

Last edit: 2013-05-14 13:24:55
Jacob Plachta: 2013-05-14 13:14:58

I don't know what's going on in the data, but I'm unable to read Q at some point. I've tried both using cin to read each string (skipping whitespace), and using getline to read each line at a time (in case some strings are empty).

Federico Lebrón: 2013-05-14 07:19:39

Input strings contain something other than 'a'...'z', checked by adding a dummy while(1) loop. Please fix.


Added by:hossamyosef
Date:2013-05-13
Time limit:0.408s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:FCIS/ASU Local Contest 2013