University of Toronto ACM-ICPC Tryouts 2012
Let's talk about some definitions, shall we?
An uppercase letter is a character between
Z, inclusive. You
A string is a sequence of characters. You probably knew that.
A Foxic letter is a superior uppercase letter - namely, one of
X. You probably didn't know that.
A Foxic string is a superior string, consisting only of Foxic letters. You didn't know that.
Finally, a Foxic expression is a special string, with each of its
characters being either a Foxic letter, or an
n immediately following
a Foxic letter. A Foxic expression can be translated into a Foxic string
by a three-step process. First, up to one character can be added,
removed, or modified, provided that the resulting string is still a
valid Foxic expression. Next, every Foxic letter immediately preceding
n is replaced by zero or more occurrences of that same letter.
n is removed. You most certainly did not know that.
There are ~T~ ~(1 \le T \le 100)~ scenarios to consider, as described above. In each scenario, given a Foxic string ~S~ of length ~N~ ~(1 \le N \le 100)~ and a Foxic expression ~E~ of length ~M~ ~(1 \le M \le 100)~, you'd like to determine whether or not ~E~ can be translated into ~S~.
Line 1: 1 integer, ~T~
For each scenario:
Line 1: 1 integer, ~N~
Line 2: 1 string, ~S~
Line 3: 1 integer, ~M~
Line 4: 1 string, ~E~
For each scenario:
Yes if ~E~ can be translated into ~S~, or
2 5 OOOFO 7 OXnFOXn 3 FOX 7 OFnOXnO
Explanation of Sample
In the first scenario, one possible course of action is to erase the
second character of ~E~, leaving the Foxic expression
OnFOXn. Next, we
may choose to replace the first
O with three copies of
O, and the
X with zero occurrences of
X, since each of these precedes
n - this yields the string
OOOnFOn. Finally, after removing each
n, we are left with
OOOFO, which matches ~S~. Replacing the second
character with an
O would have also been possible.
In the second scenario, it is impossible to translate ~E~ into ~S~ through any valid steps.