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'.


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

hide comments
2013-07-17 18:06:54 Akhilesh Anandh
Take care of the fact that the input strings may be empty. Using cin to read strings is not good enough.

Last edit: 2014-08-19 21:52:06
2013-06-17 18:27:32 Piyush Raman Srivastava
printing Case :n instead of Case n: costed me so many WA! ;p


Last edit: 2013-06-19 22:09:57
2013-05-31 19:19:19 praveen123
too strict time limit
2013-05-19 04:22:13 deinier
I think that an empty string is not valid. The problem statement says that "S and T will have letters from 'a' to 'z'".
2013-05-18 12:10:41 (Tjandra Satria Gunawan)(曾毅昆)
@Lakshman: I can't see your code, I think you set Submissons Visibility to "user" please make it "private" or "public", so I can see your code.
2013-05-18 11:59:12 [Lakshman]
Still NZEC I rectified that problem, @ Tjandra can you please see if I am reading input incorrectly
changed.done
...
RE:>>http://ideone.com/CvTxA9 Please help..
this contains only input method..

Last edit: 2013-05-18 16:54:08
2013-05-18 11:28:27 (Tjandra Satria Gunawan)(曾毅昆)
@Lakshman: Yes, there are some empty lines in input.. But you should process it as empty string..
2013-05-18 11:22:04 [Lakshman]
How to read input in Java,I am using Scanner class. On My System it is working fine also checked on ideone, here getting run time error. Can you please tell me, are there any empty lines in input file....

Last edit: 2013-05-18 11:22:57
2013-05-18 08:43:44 (Tjandra Satria Gunawan)(曾毅昆)
unexpected eof(?) I'll check this..
EDIT: my mistake
EDIT2: found my silly mistake, I forget about empty string ;-)
Finally AC :-D

Last edit: 2013-05-18 09:39:07
2013-05-15 20:05:13 Hasan Jaddouh
how much the number of test cases ?

Can O(Q(S+T))solution per test case pass?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.