Your Name is Mine
All submissions for this problem are available.
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.
The first line contains an integer T, the number of test cases. T test cases follow. Each test case contains two space separated strings M and W.
For each test case print
"YES" if they are allowed to marry, else print
"NO". (quotes are meant for clarity, please don't print them)
- 1 ≤ T ≤ 100
- 1 ≤ |M|, |W| ≤ 25000 (|A| denotes the length of the string A.)
- All names consist of lowercase English letters only.
Input: 3 john johanna ira ira kayla jayla Output: YES YES NO
Case 1: Consider S = "johanna". So, S = 'j', S = 'o', S = '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".
|Tags||ad-hoc, cakewalk, kaushik_iska, may13|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.