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.
|
|
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?
|
|
Xsquare:
2013-05-14 13:24:39
In full agreement with you both, Jacob Plachta and Federico Lebron!
|
|
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 |