Unfortunately, this task has no story because my dog ate some of my notes. Instead, you’ll get to help me determine whether I can salvage something out of the scraps left after the dog ran away.
You are given two strings A and B. Find whether B is a subsequence of A.
The subsequence does not need to be contiguous. In other words, your task is to find whether it is possible to change A into B by erasing some (possibly none) of its characters.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains the string A. The second line contains the string B. Both strings consist only of uppercase English letters.
In the easy subproblem S1 the string A has length at most 100 and the string B has length 3.
In the hard subproblem S2 the string A has length at most 100, 000 and the string B has length at most 10, 000. Note that you cannot download the input for subproblem S2 directly. Instead, we have provided a small Python 2 program that will generate the file s2.in when executed.
For each test case, output a single line with a single word: “YES” or “NO” (quotes for clarity).
In the real contest, some large input files may be provided in the same way as the input s2.in in this practice problem. Please make sure you are able to generate it.
Input:
3
DAOBCCCCGS
DOG
ABCDEF
ACEG
CAT
CTAOutput:
YES
NO
NO