DICTSUB - Dictionary Subsequences
You have a dictionary of strings, and you want to perform some queries on the strings. In particular, you're given a single string T, and for each word W in the dictionary, you want to determine if W is a subsequence of T.
A string B is a subsequence of a string C if you can remove zero or more of C's letters to form a string equal to B (but the order of remaining letters may not be rearranged).
Each word W in the dictionary will be described in the input as a run length encoded (RLE) string. That is, W will be described by several pairs of data values, where each pair of data values consists of a positive integer K
with no leading zeros and a letter L. A data pair with values K and L represents a string with K occurrences of the character L. To get the uncompressed string, we concatenate all strings represented by the data pairs.
For example, the RLE string 2A1B5C12A represents the string AABCCCCCAAAAAAAAAAAA.
Input
The first line of the input contains a positive integer C (0 < C < 10), the number of test cases to follow. Each case begins with a line containing a positive integer D (0 < D < 10000) representing the number of dictionary words and a string T with length between 1 and 10000. D lines follow, with each line containing a string with length between 1 and 200 in RLE format, which represents a dictionary word with uncompressed length between 1 and 10000. All uncompressed strings (T and dictionary words) will consist only of uppercase letters ('A'-'Z').
Output
Output for each case consists of several lines. There should be one line per dictionary word W (in the order of appearance in input) that will say either "YES" if W is a subsequence of T, or "NO" otherwise. Print a blank line after each test case.
Example
Input: 1 5 EFFERVESCENCE 2E 1E1F1V1C1E 1E2F1C1R 1S2E 1P1E2F Output: YES YES NO YES NO
hide comments
The_ROCK:
2015-01-28 22:30:55
time limit is strict. use scanf/printf in c++ |
|
Balrog:
2010-06-04 01:16:46
there must have /r in the end of the line.... - - |
Added by: | eleusive |
Date: | 2008-10-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Al-Khawarizm 2008 - Set by eleusive |