SPOJ Problem Set (classical)
3106. Dictionary Subsequences
Problem code: DICTSUB
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.
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 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.
|Added by:||John Rizzo|
Cube (Intel Pentium G860 3GHz)
|Languages:||All except: ERL JS NODEJS PERL 6 SCM chicken VB.net |
|Resource:||Al-Khawarizm 2008 - Set by eleusive|