7364: CodeChef NAME2 - Your Name is Mine
Description
In an attempt to control the rise in population, Archer was asked to come up with a plan. This time he is targeting marriages. Archer, being as intelligent as he is, came up with the following plan:
A man with name M is allowed to marry a woman with name W, only if M is a subsequence of W or W is a subsequence of M.
A is said to be a subsequence of B, if A can be obtained by deleting some elements of B without changing the order of the remaining elements.
Your task is to determine whether a couple is allowed to marry or not, according to Archer's rule.
Input
Each test case contains two space separated strings M and W.
Output
Constraints
1 ≤ |M|, |W| ≤ 25000 (|A| denotes the length of the string A.)
All names consist of lowercase English letters only.
Sample 1 Input
3
john johanna
ira ira
kayla jayla
Sample 1 Output
YES
YES
NO
Case 1: Consider S = "johanna". So, S[0] = 'j', S[1] = 'o', S[2] = 'h' and so on. If we remove the indices [3, 4, 6] or [3, 5, 6] from S, it becomes "john". Hence "john" is a subsequence of S, so the answer is "YES".
Case 2: Any string is a subsequence of it self, as it is formed after removing "0" characters. Hence the answer is "YES".
Case 3: "jayla" can not be attained from "kayla" as removing any character from "kayla" would make the string length smaller than "jayla", also there is no 'j' in "kayla". Similar reasoning can be applied to see why "kayla" can't be attained from "jayla". Hence the answer is "NO".