| Submit | All submissions | Best solutions | Back to list |
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-05-15 18:24:30 Xsquare
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! |
||||||
|
2013-05-15 07:12:46 nitish rao
thank you.. Federico Lebrón :) :) Last edit: 2013-05-15 07:57:49 |
||||||
|
2013-05-15 02:15:08 Federico Lebrón
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 |
||||||
|
2013-05-15 00:35:31 hossamyosef
this problem had been solved by many teams at our contest , please read problem statement well , and try to solve it again :) |
||||||
|
2013-05-14 15:32:37 Federico Lebrón
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. |
||||||
|
2013-05-14 13:24:39 Xsquare
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 |
||||||
|
2013-05-14 13:14:58 Jacob Plachta
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). |
||||||
|
2013-05-14 07:19:39 Federico Lebrón
Input strings contain something other than 'a'...'z', checked by adding a dummy while(1) loop. Please fix. |
||||||
RSS