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 ------ 

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.

------ Output ------ 

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)

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ |M|, |W| ≤ 25000 (|A| denotes the length of the string A.)$
$All names consist of lowercase English letters only.$

----- Sample Input 1 ------ 
3
john johanna
ira ira
kayla jayla
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
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".

Difficulty: EASY
Tags: Constructive algorithms

String algorithms

Amortized analysis

Dynamic programming

Data structures

Ad-hoc
Skill types: Dynamic programming

Data structures

Amortized analysis

Starter code:

Solutions:
def solve(a, b):
	i = 0
	j = 0
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			j += 1
	if i == len(a):
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	(w, m) = map(str, input().split())
	if len(m) > len(w):
		print(solve(w, m))
	else:
		print(solve(m, w))


for _ in range(int(input())):
	(m, w) = input().split()
	a = len(m)
	b = len(w)
	if b > a:
		(a, b) = (b, a)
		(m, w) = (w, m)
	(i, j) = (0, 0)
	res = ''
	while i < a and j < b:
		if m[i] == w[j]:
			res += m[i]
			i += 1
			j += 1
		else:
			i += 1
	if res == m or res == w:
		print('YES')
	else:
		print('NO')


def is_subsequence(a, b):
	i = j = 0
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			i += 1
		j += 1
	return i == len(a)
t = int(input())
for _ in range(t):
	(m, w) = input().split()
	if is_subsequence(m, w) or is_subsequence(w, m):
		print('YES')
	else:
		print('NO')


def subsequence(m, w):
	l1 = len(m)
	l2 = len(w)
	i = 0
	j = 0
	while i < l1 and j < l2:
		if m[i] == w[j]:
			i = i + 1
			j = j + 1
		else:
			j = j + 1
	if i == l1:
		print('YES')
	else:
		print('NO')
t = int(input())
for i in range(t):
	(m, w) = list(map(str, input().split()))
	l1 = len(m)
	l2 = len(w)
	if l1 > l2:
		subsequence(w, m)
	else:
		subsequence(m, w)


def subseq(a, b):
	n1 = len(a)
	n2 = len(b)
	i = 0
	j = 0
	while i < n1 and j < n2:
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			j += 1
	if i == n1:
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	(x, y) = map(str, input().split())
	if len(x) > len(y):
		print(subseq(y, x))
	else:
		print(subseq(x, y))


def subsequence(a, b):
	i = 0
	j = 0
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			j += 1
	if i == len(a):
		return True
	else:
		return False
for _ in range(int(input())):
	(m, w) = map(str, input().strip().split())
	if subsequence(m, w) or subsequence(w, m):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(m, w) = input().split()
	k = 0
	count = 0
	for j in range(len(m)):
		s = m[j]
		while True:
			if k == len(w):
				break
			if w[k] == s:
				count += 1
				k += 1
				break
			k += 1
	if count == len(m):
		print('YES')
	else:
		k = 0
		count = 0
		for j in range(len(w)):
			s = w[j]
			while True:
				if k == len(m):
					break
				if m[k] == s:
					count += 1
					k += 1
					break
				k += 1
		if count == len(w):
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(m, w) = input().split()
	(m, w) = sorted([m, w], key=len)
	flag = False
	for i in range(len(m)):
		if m[i] not in w:
			flag = True
			break
		else:
			w = w[w.index(m[i]) + 1:]
	print('NO' if flag else 'YES')


t = int(input())
res = []
for i in range(t):
	texts = input().split(' ')
	longTx = []
	shortTx = []
	if len(texts[0]) >= len(texts[1]):
		longTx = list(texts[0])
		shortTx = list(texts[1])
	else:
		shortTx = list(texts[0])
		longTx = list(texts[1])
	for k in range(0, len(longTx)):
		if len(shortTx) < 1:
			break
		if longTx[k] == shortTx[0] and len(shortTx) > 0:
			del shortTx[0]
	if len(shortTx) > 0:
		res.append('NO')
	else:
		res.append('YES')
print('\n'.join(res))


def f(s1, s2):
	j = 0
	for i in s2:
		if i == s1[j]:
			j += 1
		if j == s1.__len__():
			return True
	return False
from sys import stdin, stdout
t = int(stdin.readline())
for j in range(t):
	(m, w) = stdin.readline().strip().split()
	out = 'YES' if f(m, w) or f(w, m) else 'NO'
	stdout.write(f'{out}\n')


def is_subsequence(a, b):
	i = 0
	for ch in b:
		if i == len(a):
			return True
		if ch == a[i]:
			i += 1
	return i == len(a)
t = int(input())
for i in range(t):
	(m, w) = input().split()
	if is_subsequence(m, w) or is_subsequence(w, m):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(x, y) = input().split()
	if len(x) > len(y):
		(x, y) = (y, x)
	i = 0
	for j in y:
		if j == x[i]:
			i += 1
		if i == len(x):
			break
	if i == len(x):
		print('YES')
	else:
		print('NO')


def is_allowed_to_marry(m, w):
	i = 0
	j = 0
	while i < len(m) and j < len(w):
		if m[i] == w[j]:
			i += 1
		j += 1
	return i == len(m)
T = int(input())
for _ in range(T):
	(m, w) = input().split()
	if is_allowed_to_marry(m, w) or is_allowed_to_marry(w, m):
		print('YES')
	else:
		print('NO')


def sub(m, w):
	n1 = len(m)
	n2 = len(w)
	(i, j) = (0, 0)
	while i < n1 and j < n2:
		if m[i] == w[j]:
			i += 1
			j += 1
		else:
			j += 1
	if i == n1:
		print('YES')
	else:
		print('NO')
n = int(input())
for i in range(n):
	list1 = input().split(' ')
	if len(list1[0]) < len(list1[1]):
		sub(list1[0], list1[1])
	else:
		sub(list1[1], list1[0])


for _ in range(int(input())):
	l = input().split()
	(a, b) = (l[0], l[1])
	if len(a) > len(b):
		(a, b) = (b, a)
	(la, lb, j) = (len(a), len(b), 0)
	res = 'NO'
	for i in range(lb):
		if a[j] == b[i]:
			j += 1
			if j == la:
				res = 'YES'
				break
		if lb - i < la - j:
			break
	print(res)


for t in range(int(input())):
	(a, b) = map(str, input().split())
	first = second = 0
	while first < len(a) and second < len(b):
		if a[first] == b[second]:
			first += 1
			second += 1
		else:
			second += 1
	if first == len(a):
		print('YES')
		continue
	first = second = 0
	while first < len(a) and second < len(b):
		if a[first] == b[second]:
			first += 1
			second += 1
		else:
			first += 1
	if second == len(b):
		print('YES')
		continue
	print('NO')


def can_marry(a, b):
	j = 0
	i = 0
	while j < len(b) and i < len(a):
		if a[i] == b[j]:
			i = i + 1
		j = j + 1
	if i == len(a):
		return 1
	else:
		return 0
t = int(input())
for ni in range(t):
	(a, b) = input().split()
	if can_marry(a, b) or can_marry(b, a):
		print('YES')
	else:
		print('NO')


b = int(input())
for i in range(b):
	a = list(input())
	c = []
	d = []
	o = []
	k = a.index(' ')
	if k >= len(a) // 2:
		c = a[0:k]
		d = a[k + 1:]
	else:
		d = a[0:k]
		c = a[k + 1:]
	f = 'YES'
	i = 0
	k = 0
	t = []
	j = 0
	for i in c:
		if j <= len(d) - 1:
			if i == d[j]:
				j = j + 1
		else:
			break
	if j == len(d):
		print('YES')
	else:
		print('NO')


def ans(M, N):
	t = 0
	if len(M) < len(N):
		for i in range(len(N)):
			if N[i] == M[t]:
				t += 1
			if t == len(M) - 1:
				return 'YES'
		if t == len(M) - 1:
			return 'YES'
		else:
			return 'NO'
	else:
		for i in range(len(M)):
			if M[i] == N[t]:
				t += 1
			if t == len(N) - 1:
				return 'YES'
		if t == len(N) - 1:
			return 'YES'
		else:
			return 'NO'
T = int(input())
for i in range(T):
	(a, b) = input().split(' ')
	M = list(a)
	N = list(b)
	print(ans(M, N))


T = int(input())
for _ in range(T):
	(cow, cew) = input().split()
	len_cow = len(cow)
	len_cew = len(cew)
	if len_cow > len_cew:
		tanda = 0
		poin = 0
		for i in range(len_cew):
			skrg = cew[i]
			for j in range(tanda, len_cow):
				if cow[j] == skrg:
					tanda = j + 1
					poin += 1
					break
		if poin == len_cew:
			print('YES')
		else:
			print('NO')
	elif len_cow <= len_cew:
		tanda = 0
		poin = 0
		for i in range(len_cow):
			skrg = cow[i]
			for j in range(tanda, len_cew):
				if cew[j] == skrg:
					tanda = j + 1
					poin += 1
					break
		if poin == len_cow:
			print('YES')
		else:
			print('NO')


n = int(input())
for _ in range(n):
	(a, b) = map(str, input().split())
	alen = len(a)
	blen = len(b)
	if alen > blen:
		(a, b) = (b, a)
		(alen, blen) = (blen, alen)
	i = j = 0
	while i < alen and j < blen:
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			j += 1
	if i == alen:
		print('YES')
	else:
		print('NO')


n = int(input())
for _ in range(n):
	(a, b) = input().strip().split()
	if a == b:
		print('YES')
	elif len(a) == len(b):
		print('NO')
	else:
		if len(a) < len(b):
			x = a
			y = b
		else:
			x = b
			y = a
		j = 0
		for ltr in y:
			if x[j] == ltr:
				j += 1
			if j == len(x):
				print('YES')
				break
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(s1, s2) = list(map(str, input().split()))
	if len(s1) > len(s2):
		(l, s) = (s1, s2)
	else:
		(l, s) = (s2, s1)
	result = 'YES'
	n = 0
	while n < len(s):
		char = s[n]
		if char in l:
			index = l.index(char)
			l = l[index + 1:]
		else:
			result = 'NO'
			break
		n += 1
	print(result)


def is_subsequence(subseq, seq):
	(i, j) = (0, 0)
	while i < len(subseq) and j < len(seq):
		if subseq[i] == seq[j]:
			i += 1
		j += 1
	return i == len(subseq)
for _ in range(int(input())):
	(m, w) = map(str, input().split(' '))
	a = list(m)
	b = list(w)
	if len(a) > len(b):
		print('YES' if is_subsequence(b, a) else 'NO')
	else:
		print('YES' if is_subsequence(a, b) else 'NO')


for i in range(int(input())):
	(s1, s2) = map(str, input().split())
	i = 0
	j = 0
	if len(s1) > len(s2):
		(s1, s2) = (s2, s1)
	while i < len(s1) and j < len(s2):
		if s1[i] == s2[j]:
			i = i + 1
			j = j + 1
		else:
			j = j + 1
	if i == len(s1):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	l = input().split()
	l.sort(key=len)
	m = l[0]
	n = l[1]
	k = len(n)
	kk = len(m)
	j = 0
	i = 0
	while j < kk and i < k:
		if m[j] == n[i]:
			j = j + 1
			i = i + 1
		else:
			i = i + 1
	if j == kk:
		print('YES')
	else:
		print('NO')


t = int(input())
for abc in range(t):
	(m, w) = map(str, input().split())
	if len(w) >= len(m):
		minstr = m
		maxstr = w
	else:
		minstr = w
		maxstr = m
	c = 0
	d = 0
	ans = 'YES'
	while c < len(minstr) and d < len(maxstr):
		if minstr[c] == maxstr[d]:
			c += 1
			d += 1
		else:
			d += 1
	if c == len(minstr):
		print('YES')
	else:
		print('NO')


def ijoin(array, char=' '):
	return char.join([str(x) for x in array])

def solve(m, n):
	x = 0
	y = 0
	while True:
		if y == len(n):
			return True
		elif x == len(m):
			return False
		elif m[x] == n[y]:
			x += 1
			y += 1
		else:
			x += 1
for t in range(int(input())):
	(m, n) = input().split()
	if len(n) > len(m):
		(m, n) = (n, m)
	if solve(m, n):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(m, w) = list(map(str, input().split()))
	if len(m) >= len(w):
		(x, y) = (m, w)
	else:
		(x, y) = (w, m)
	if y[0] in x:
		x = x[1:len(x)]
		for j in range(1, len(y)):
			if y[j] not in x:
				print('NO')
				break
			x = x[x.index(y[j]) + 1:len(x)]
		else:
			print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(c, d) = map(str, input().split())
	if len(c) < len(d):
		a = c
		b = d
	else:
		a = d
		b = c
	l = []
	ll = []
	s1 = s2 = 0
	cc = k = j = 0
	for i in a:
		l.append(i)
	for i in b:
		ll.append(i)
	while True:
		if cc == len(l) or k == len(ll):
			break
		if l[j] == ll[k]:
			cc += 1
			k += 1
			j += 1
		elif l[j] != ll[k]:
			k += 1
	if cc == len(l):
		print('YES')
	else:
		print('NO')


def is_subsequence(m, w):
	(i, j) = (0, 0)
	while i < len(m) and j < len(w):
		if m[i] == w[j]:
			i += 1
		j += 1
	return i == len(m)
T = int(input())
for i in range(T):
	(M, W) = input().split()
	if is_subsequence(M, W) or is_subsequence(W, M):
		print('YES')
	else:
		print('NO')


def helper(A, B):
	len1 = len(A)
	len2 = len(B)
	(i, j) = (0, 0)
	while i < len1 and j < len2:
		if A[i] == B[j]:
			i += 1
			j += 1
		else:
			j += 1
	if i == len1:
		return 'YES'
	else:
		return 'NO'
T = int(input())
while T > 0:
	T -= 1
	(M, W) = input().split()
	if len(W) > len(M):
		print(helper(M, W))
	else:
		print(helper(W, M))


def match(a, b):
	p1 = p2 = 0
	while p1 < len(a) and p2 < len(b):
		if a[p1] == b[p2]:
			p1 += 1
			p2 += 1
		else:
			p2 += 1
	if p1 == len(a):
		return True
	return False
for _ in range(int(input())):
	(M, W) = input().split()
	flag = match(M, W)
	if not flag:
		flag = match(W, M)
	print('YES' if flag else 'NO')


t = int(input())
for _ in range(t):
	(a, b) = sorted(input().split(), key=len)
	if a in b:
		print('YES')
		continue
	i = 0
	for k in b:
		if k == a[i]:
			i += 1
		if i == len(a):
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	(a, b) = input().split()
	if len(a) > len(b):
		(a, b) = (b, a)
	ans = 'YES'
	for i in a:
		try:
			c = b.index(i)
			b = b[c + 1:]
		except:
			ans = 'NO'
	print(ans)


testcases = int(input())
while testcases:
	[M, W] = list(map(str, input().split()))
	len_M = len(M)
	len_W = len(W)
	i = 0
	for char_W in W:
		if i >= len_M - 1:
			break
		if M[i] == char_W:
			i += 1
	if i + 1 == len_M:
		print('YES')
		testcases -= 1
		continue
	i = 0
	for char_M in M:
		if i >= len_W - 1:
			break
		if W[i] == char_M:
			i += 1
	if i + 1 == len_W:
		print('YES')
		testcases -= 1
		continue
	print('NO')
	testcases -= 1


def sub_seq(a, b, la, lb):
	i = 0
	j = 0
	count = 0
	while i < la and j < lb:
		if a[i] == b[j]:
			i += 1
			j += 1
			count += 1
		else:
			i += 1
	if count == lb:
		print('YES')
	else:
		print('NO')
t = int(input())
for x in range(0, t):
	(m, w) = map(str, input().split(' '))
	lm = len(m)
	lw = len(w)
	if lm > lw:
		sub_seq(m, w, lm, lw)
	else:
		sub_seq(w, m, lw, lm)


def is_subseq(sub, seq):
	i = 0
	for char in seq:
		if char == sub[i]:
			i += 1
			if i == len(sub):
				return True
	return False
t = int(input())
for _ in range(0, t):
	(m, w) = input().split()
	ans = is_subseq(m, w) if len(m) < len(w) else is_subseq(w, m)
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(x, y) = input().split(' ')
	n = len(x)
	m = len(y)
	if n < m:
		(n, m) = (m, n)
		(x, y) = (y, x)
	i = 0
	j = 0
	ans = ''
	while i < n and j < m:
		if x[i] == y[j]:
			ans += x[i]
			i += 1
			j += 1
		else:
			i += 1
	if ans == x or ans == y:
		print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	arr = input().split()
	arr = sorted(arr, key=len)
	count = 0
	itr = 0
	if len(arr[0]) != len(arr[1]):
		M = arr[0]
		W = arr[1]
	elif arr[0] == arr[1]:
		print('YES')
		continue
	else:
		print('NO')
		continue
	while itr < len(W):
		if M[count] == W[itr]:
			count += 1
		itr += 1
		if count == len(M):
			print('YES')
			break
	if count != len(M):
		print('NO')


def match(a, b):
	t = 0
	for i in range(len(b)):
		if b[i] == a[t]:
			t += 1
		if t == len(a):
			return 1
	return 0
for i in range(int(input())):
	(a, b) = input().split()
	print(['NO', 'YES'][match(a, b) or match(b, a)])