Foxic Expressions

View as PDF

Submit solution

Points: 15
Time limit: 9.0s
Memory limit: 64M

Problem types
University of Toronto ACM-ICPC Tryouts 2012

Let's talk about some definitions, shall we?

An uppercase letter is a character between A and Z, inclusive. You knew that.

A string is a sequence of characters. You probably knew that.

A Foxic letter is a superior uppercase letter - namely, one of F, O, or 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 an n is replaced by zero or more occurrences of that same letter. Finally, each 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.

Input Specification

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

Output Specification

For each scenario:
Line 1: Yes if E can be translated into S, or No otherwise.

Sample Input


Sample Output


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 remaining X with zero occurrences of X, since each of these precedes an 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.


There are no comments at the moment.