You are given two strings s and t. Now your task is to print all longest common sub-sequences in lexicographical order.
Example 1:
Input: s = abaaa, t = baabaca
Output: aaaa abaa baaa
Example 2:
Input: s = aaa, t = a
Output: a
Your Task:
You do not need to read or print anything. Your task is to complete the function all_longest_common_subsequences() which takes string a and b as first and second parameter respectively and returns a list of strings which contains all possible longest common subsequences in lexicographical order.
 
Expected Time Complexity: O(n^{4})
Expected Space Complexity: O(K * n) where K is a constant less than n.
 
Constraints:
1 ≤ Length of both strings ≤ 50

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Complete search

Starter code: #User function Template for python3



class Solution:

	def all_longest_common_subsequences(self, s, t):

		# Code here



Solutions:
class Solution:

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][0] = 0
		for j in range(1, m + 1):
			dp[0][j] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		maxi = dp[n][m]

		def printing(i, j, temp, res, maxi):
			if maxi == 0:
				if temp not in res:
					res.append(temp)
				return
			if i >= len(s) or j >= len(t):
				return
			for row in range(i, len(s)):
				for col in range(j, len(t)):
					if s[row] == t[col]:
						temp += s[row]
						printing(row + 1, col + 1, temp, res, maxi - 1)
						temp = temp[:-1]
		res = []
		printing(0, 0, '', res, maxi)
		res.sort()
		return res


from collections import deque

class Solution:

	def dfs(self, i, j, temp, dp, st, marked, text1, text2):
		if i == 0 or j == 0:
			st.add(temp)
			return
		if (i, j, temp) in marked:
			return
		marked.add((i, j, temp))
		if text1[i - 1] == text2[j - 1]:
			self.dfs(i - 1, j - 1, text1[i - 1] + temp, dp, st, marked, text1, text2)
		elif dp[i - 1][j] == dp[i][j - 1]:
			self.dfs(i - 1, j, temp, dp, st, marked, text1, text2)
			self.dfs(i, j - 1, temp, dp, st, marked, text1, text2)
		elif dp[i - 1][j] > dp[i][j - 1]:
			self.dfs(i - 1, j, temp, dp, st, marked, text1, text2)
		else:
			self.dfs(i, j - 1, temp, dp, st, marked, text1, text2)

	def all_longest_common_subsequences(self, text1, text2):
		(n, m) = (len(text1), len(text2))
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					left = dp[i - 1][j]
					right = dp[i][j - 1]
					dp[i][j] = max(left, right)
		st = set()
		self.dfs(n, m, '', dp, st, set(), text1, text2)
		res = list(st)
		res.sort()
		return res


class Solution:

	def all_longest_common_subsequences(self, str1, str2):
		MAX = 100
		lcslen = 0
		dp = [[-1 for i in range(MAX)] for i in range(MAX)]

		def lcs(str1, str2, len1, len2, i, j):
			if i == len1 or j == len2:
				dp[i][j] = 0
				return dp[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			ret = 0
			if str1[i] == str2[j]:
				ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1)
			else:
				ret = max(lcs(str1, str2, len1, len2, i + 1, j), lcs(str1, str2, len1, len2, i, j + 1))
			dp[i][j] = ret
			return ret
		res = []

		def printAll(str1, str2, len1, len2, data, indx1, indx2, currlcs):
			if currlcs == lcslen:
				res.append(''.join(data[:currlcs]))
				return
			if indx1 == len1 or indx2 == len2:
				return
			for ch in range(ord('a'), ord('z') + 1):
				done = False
				for i in range(indx1, len1):
					if chr(ch) == str1[i]:
						for j in range(indx2, len2):
							if chr(ch) == str2[j] and dp[i][j] == lcslen - currlcs:
								data[currlcs] = chr(ch)
								printAll(str1, str2, len1, len2, data, i + 1, j + 1, currlcs + 1)
								done = True
								break
					if done:
						break
		(len1, len2) = (len(str1), len(str2))
		lcslen = lcs(str1, str2, len1, len2, 0, 0)
		data = ['a' for i in range(MAX)]
		printAll(str1, str2, len1, len2, data, 0, 0, 0)
		return res


class Solution:

	def all_longest_common_subsequences(self, s, t):
		dp = [[set() for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
		for i in range(1, len(s) + 1):
			for j in range(1, len(t) + 1):
				if s[i - 1] == t[j - 1]:
					if len(dp[i - 1][j - 1]) == 0:
						dp[i][j].add(s[i - 1])
					else:
						dp[i][j] = {x + s[i - 1] for x in dp[i - 1][j - 1]}
				else:
					dp[i][j] = dp[i - 1][j].union(dp[i][j - 1])
		sets = dp[len(s)][len(t)]
		if len(sets) == 0:
			return []
		max_len = len(max(sets, key=len))
		return sorted([x for x in sets if len(x) == max_len])


class Solution:

	def all_longest_common_subsequences(self, s, t):
		x = len(s)
		y = len(t)
		dp = [[-1 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for ind1 in range(1, x + 1, 1):
			for ind2 in range(1, y + 1, 1):
				if s[ind1 - 1] == t[ind2 - 1]:
					dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
				else:
					dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
		res = []
		self.process(s, t, 0, 0, dp[x][y], '', res, x, y)
		res = list(set(res))
		res.sort()
		return res

	def process(self, s1, s2, ind1, ind2, lcslen, curlcs, res, x, y):
		if len(curlcs) == lcslen:
			res.append(curlcs)
			return
		if ind1 >= x or ind2 >= y:
			return
		for i in range(ind1, x, 1):
			for j in range(ind2, y, 1):
				if s1[i] == s2[j]:
					self.process(s1, s2, i + 1, j + 1, lcslen, curlcs + s1[i], res, x, y)


class Solution:

	def all_longest_common_subsequences(self, s: str, t: str):
		(m, n) = (len(s), len(t))
		dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs_len = dp[m][n]
		res_set = set()
		self.printSeq(s, t, 0, 0, '', res_set, lcs_len)
		res = sorted(list(res_set))
		return res

	def printSeq(self, s, t, m, n, seq, res_set, lcs_len):
		if lcs_len == 0:
			res_set.add(seq)
			return
		if m >= len(s) or n >= len(t):
			return
		for i in range(m, len(s)):
			for j in range(n, len(t)):
				if s[i] == t[j]:
					self.printSeq(s, t, i + 1, j + 1, seq + s[i], res_set, lcs_len - 1)


from itertools import product

class Solution:

	def all_longest_common_subsequences(self, s, t):
		(n, m) = map(len, (s, t))
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for (i, j) in product(*map(range, (n, m))):
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
			if s[i] == t[j]:
				dp[i + 1][j + 1] = max(dp[i + 1][j + 1], 1 + dp[i][j])
		ln = dp[-1][-1]
		res = []

		def fun(i=0, j=0, ln=ln, path=''):
			nonlocal res
			if not ln:
				if path not in res:
					res.append(path)
				return
			if i >= n or j >= m:
				return
			for x in range(i, n):
				for y in range(j, m):
					if s[x] == t[y]:
						path += s[x]
						fun(x + 1, y + 1, ln - 1, path)
						path = path[:-1]
		fun()
		return sorted(res)


class Solution:

	def __init__(self):
		self.st = set()

	def all_longest_common_subsequences(self, s, t):
		x = len(s)
		y = len(t)
		dp = [[-1] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			dp[i][0] = 0
		for j in range(y + 1):
			dp[0][j] = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		maxi = dp[x][y]

		def printing(i, j, temp, res, maxi):
			if maxi == 0:
				if temp not in self.st:
					self.st.add(temp)
					res.append(temp)
				return
			if i >= len(s) or j >= len(t):
				return
			for row in range(i, len(s)):
				for col in range(j, len(t)):
					if s[row] == t[col]:
						temp += s[row]
						printing(row + 1, col + 1, temp, res, maxi - 1)
						temp = temp[:-1]
		res = []
		printing(0, 0, '', res, maxi)
		res.sort()
		return res


class Solution:

	def all_longest_common_subsequences(self, s, t):
		dp = {}
		(n, m) = (len(s), len(t))

		def q(i, j):
			if i == n or j == m:
				dp[i, j] = 0
				return 0
			if (i, j) in dp:
				return dp[i, j]
			ans = 0
			if s[i] == t[j]:
				ans = 1 + q(i + 1, j + 1)
			dp[i, j] = max(ans, q(i + 1, j), q(i, j + 1))
			return dp[i, j]
		se = set()
		v = set()

		def f(z, i=0, j=0, S=''):
			if (i, j, S) in v:
				return
			v.add((i, j, S))
			if i == n or j == m:
				se.add(S)
				return
			if s[i] == t[j] and dp[i + 1, j + 1] == z - 1:
				f(z - 1, i + 1, j + 1, S + s[i])
			if dp[i + 1, j] == z:
				f(z, i + 1, j, S)
			if dp[i, j + 1] == z:
				f(z, i, j + 1, S)
		f(q(0, 0))
		return sorted(se)


class Solution:

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] += max(dp[i - 1][j], dp[i][j - 1])
		res = []
		self.process(s, t, 0, 0, dp[n][m], '', res, n, m)
		res = list(set(res))
		res.sort()
		return res

	def process(self, s1, s2, i, j, lcslen, curlcs, res, n, m):
		if len(curlcs) == lcslen:
			res.append(curlcs)
			return
		if i >= n or j >= m:
			return
		for a in range(i, n, 1):
			for b in range(j, m, 1):
				if s1[a] == s2[b]:
					self.process(s1, s2, a + 1, b + 1, lcslen, curlcs + s1[a], res, n, m)


class Solution:

	def all_longest_common_subsequences(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[[]] * (n + 1) for i in range(m + 1)]
		for i in range(0, m + 1):
			for j in range(0, n + 1):
				if i == 0 or j == 0:
					dp[i][j] = ['']
				elif s1[i - 1] == s2[j - 1]:
					temp_lis = []
					for temp in dp[i - 1][j - 1]:
						temp_lis.append(temp + s2[j - 1])
					dp[i][j] = temp_lis
				else:
					temp_1 = dp[i - 1][j]
					temp_2 = dp[i][j - 1]
					temp_lis = []
					if len(temp_1) > 0 and len(temp_2) > 0:
						if len(temp_1[0]) > len(temp_2[0]):
							for temp in temp_1:
								temp_lis.append(temp)
						elif len(temp_2[0]) > len(temp_1[0]):
							for temp in temp_2:
								temp_lis.append(temp)
						else:
							for temp in temp_1:
								temp_lis.append(temp)
							for temp in temp_2:
								temp_lis.append(temp)
						dp[i][j] = list(set(temp_lis))
		return sorted(dp[-1][-1])


class Solution:

	def all_longest_common_subsequences(self, s, t):
		dp = [[[]] * (len(t) + 1) for i in range(len(s) + 1)]
		for i in range(0, len(s) + 1):
			for j in range(0, len(t) + 1):
				if i == 0 or j == 0:
					dp[i][j] = ['']
				elif s[i - 1] == t[j - 1]:
					temp_lis = []
					for temp in dp[i - 1][j - 1]:
						temp_lis.append(temp + t[j - 1])
					dp[i][j] = temp_lis
				else:
					temp_1 = dp[i - 1][j]
					temp_2 = dp[i][j - 1]
					temp_lis = []
					if len(temp_1) > 0 and len(temp_2) > 0:
						if len(temp_1[0]) > len(temp_2[0]):
							for temp in temp_1:
								temp_lis.append(temp)
						elif len(temp_2[0]) > len(temp_1[0]):
							for temp in temp_2:
								temp_lis.append(temp)
						else:
							for temp in temp_1:
								temp_lis.append(temp)
							for temp in temp_2:
								temp_lis.append(temp)
						dp[i][j] = list(set(temp_lis))
		return sorted(dp[-1][-1])


class Solution:

	def tabular(self, text1, text2):
		n = len(text1)
		m = len(text2)
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		result = []
		se = set()
		self.process(text1, text2, 0, 0, [], result, dp[-1][-1], se)
		result.sort()
		return result

	def process(self, s, t, i, j, temp, ans, count, se):
		temp1 = ''.join(temp)
		if count == 0:
			if temp1 not in se:
				se.add(temp1)
				ans.append(temp1)
			return
		if i >= len(s) or j >= len(t):
			return
		for r in range(i, len(s)):
			for c in range(j, len(t)):
				if s[r] == t[c]:
					temp.append(s[r])
					self.process(s, t, r + 1, c + 1, temp, ans, count - 1, se)
					temp.pop()

	def all_longest_common_subsequences(self, s, t):
		return self.tabular(text1=s, text2=t)


class Solution:

	def solve(self, s, t, i, j, temp, ans, count, se):
		if count == 0:
			if temp not in se:
				se.add(temp)
				ans.append(temp)
			return
		if i >= len(s) or j >= len(t):
			return
		for r in range(i, len(s)):
			for c in range(j, len(t)):
				if s[r] == t[c]:
					temp += s[r]
					self.solve(s, t, r + 1, c + 1, temp, ans, count - 1, se)
					temp = temp[:-1]

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		se = set()
		count = dp[n][m]
		ans = []
		temp = ''
		self.solve(s, t, 0, 0, temp, ans, count, se)
		ans.sort()
		return ans


class Solution:

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if t[j - 1] == s[i - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		l = dp[n][m]
		d1 = ['a' for i in range(51)]
		r = []

		def solve(i, j, cl, r, d1):
			if cl == l:
				r.append(''.join(d1[:cl]))
				return
			if i == n or j == m:
				return
			for c in range(ord('a'), ord('z') + 1):
				x = False
				for p in range(i, n):
					if chr(c) == s[p]:
						for q in range(j, m):
							if s[p] == t[q] and dp[p + 1][q + 1] == cl + 1:
								d1[cl] = s[p]
								solve(p + 1, q + 1, cl + 1, r, d1)
								x = True
								break
					if x:
						break
		solve(0, 0, 0, r, d1)
		return r


class Solution:

	def all_longest_common_subsequences(self, s, t):
		l1 = len(s)
		l2 = len(t)
		memo = [[-1] * (l2 + 1) for _ in range(l1 + 1)]
		for i in range(l1 + 1):
			memo[i][0] = 0
		for j in range(l2 + 1):
			memo[0][j] = 0
		max_ = -1
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				if s[i - 1] == t[j - 1]:
					memo[i][j] = 1 + memo[i - 1][j - 1]
				else:
					memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])
		result = []
		v = set()

		def backtrack(i, j, string):
			if (i, j, string) in v:
				return
			v.add((i, j, string))
			if i == 0 or j == 0:
				if string not in result:
					result.append(string)
				return
			if s[i - 1] == t[j - 1]:
				new_string = s[i - 1] + string
				backtrack(i - 1, j - 1, new_string)
			elif memo[i - 1][j] > memo[i][j - 1]:
				backtrack(i - 1, j, string)
			elif memo[i][j - 1] > memo[i - 1][j]:
				backtrack(i, j - 1, string)
			else:
				backtrack(i - 1, j, string)
				backtrack(i, j - 1, string)
		backtrack(l1, l2, '')
		result.sort()
		return result


def lcs(A, B, i, j, dp):
	if i == len(A) or j == len(B):
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	ans = 0
	if A[i] == B[j]:
		ans = 1 + lcs(A, B, i + 1, j + 1, dp)
	else:
		ans = max(lcs(A, B, i + 1, j, dp), lcs(A, B, i, j + 1, dp))
	dp[i][j] = ans
	return ans

def f(A, B, temp, i, j, size, res, dp):
	if size == 0:
		res.append(temp)
		return
	if i == len(A) or j == len(B):
		return
	for c in range(ord('a'), ord('z') + 1):
		ff = False
		for p in range(i, len(A)):
			ch = chr(c)
			if ch == A[p]:
				for q in range(j, len(B)):
					if B[q] == ch and dp[p][q] == size:
						f(A, B, temp + ch, p + 1, q + 1, size - 1, res, dp)
						ff = True
						break
			if ff:
				break

class Solution:

	def all_longest_common_subsequences(self, s, t):
		dp = [[-1 for i in range(51)] for i in range(51)]
		res = []
		size = lcs(s, t, 0, 0, dp)
		f(s, t, '', 0, 0, size, res, dp)
		return res


class Solution:

	def all_longest_common_subsequences(self, s1, s2):
		x = len(s1)
		y = len(s2)
		l = [[0 for i in range(y + 1)] for j in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					l[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					l[i][j] = l[i - 1][j - 1] + 1
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
		n = l[x][y]
		l = set()
		m = {}

		def add_subsequences(i, j, x, y, t, l, n):
			if len(t) == n:
				l.add(t)
				return
			if i >= x or j >= y:
				return
			for k in range(i, x):
				for m in range(j, y):
					if s1[k] == s2[m]:
						add_subsequences(k + 1, m + 1, x, y, t + s1[k], l, n)
		add_subsequences(0, 0, x, y, '', l, n)
		l = list(l)
		l.sort()
		return l


class Solution:

	def all_longest_common_subsequences(self, s1, s2):
		MAX = 100
		dp = [[-1 for i in range(MAX)] for i in range(MAX)]

		def lcs(str1, str2, len1, len2, i, j):
			if i == len1 or j == len2:
				dp[i][j] = 0
				return dp[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			ret = 0
			if str1[i] == str2[j]:
				ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1)
			else:
				ret = max(lcs(str1, str2, len1, len2, i + 1, j), lcs(str1, str2, len1, len2, i, j + 1))
			dp[i][j] = ret
			return ret

		def printAll(str1, str2, len1, len2, cur, indx1, indx2, currlcs, lcslen):
			if currlcs == lcslen:
				ans.append(cur)
				return
			if indx1 == len1 or indx2 == len2:
				return
			for ch in range(ord('a'), ord('z') + 1):
				done = False
				for i in range(indx1, len1):
					if chr(ch) == str1[i]:
						for j in range(indx2, len2):
							if chr(ch) == str2[j] and dp[i][j] == lcslen - currlcs:
								new_cur = cur + chr(ch)
								printAll(str1, str2, len1, len2, new_cur, i + 1, j + 1, currlcs + 1, lcslen)
								done = True
								break
							if done:
								break
		(len1, len2) = (len(s), len(t))
		lcslen = lcs(s, t, len1, len2, 0, 0)
		global ans
		ans = []
		printAll(s, t, len1, len2, '', 0, 0, 0, lcslen)
		ans.sort()
		w = set()
		pre = []
		for i in ans:
			if i in w:
				continue
			else:
				pre.append(i)
				w.add(i)
		return pre
		x = len(s1)
		y = len(s2)

		def make(m, n, temp, x, y):
			while m <= x and n <= y:
				if s1[m - 1] == s2[n - 1]:
					temp += s1[m - 1]
					m += 1
					n += 1
				elif dp[m - 1][n] > dp[m][n - 1]:
					m += 1
				elif dp[m - 1][n] < dp[m][n - 1]:
					n += 1
				else:
					make(m + 1, n, temp, x, y)
					make(m, n + 1, temp, x, y)
					m += 1
					n += 1
			if len(temp) == dp[-1][-1]:
				res.add(temp)
			return
		dp = [[0] * (y + 1) for i in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		res = set()
		make(1, 1, '', x, y)
		l = sorted(list(res))
		return l


class Solution:

	def all_longest_common_subsequences(self, s, t):
		ans = set()
		flag = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
		for i in range(1, len(s) + 1):
			for j in range(1, len(t) + 1):
				if s[i - 1] == t[j - 1]:
					flag[i][j] = flag[i - 1][j - 1] + 1
				else:
					flag[i][j] = max(flag[i][j - 1], flag[i - 1][j])
		dp = [[None for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

		def solve(i, j, temp, ans):
			if len(temp) == max_len:
				ans.add(temp)
				return
			if i >= len(s) or j >= len(t):
				return
			for ind1 in range(i, len(s)):
				for ind2 in range(j, len(t)):
					if s[ind1] == t[ind2]:
						solve(ind1 + 1, ind2 + 1, temp + s[ind1], ans)
		max_len = flag[len(s)][len(t)]
		solve(0, 0, '', ans)
		ans = list(ans)
		ans.sort()
		return ans


class Solution:

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for j in range(m + 1):
			dp[0][j] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		res = []

		def func(ind1, ind2, st, n, m):
			if len(st) == dp[n][m]:
				res.append(st)
				return
			if ind1 >= n or ind2 >= m:
				return
			for i in range(ind1, n):
				for j in range(ind2, m):
					if s[i] == t[j]:
						func(i + 1, j + 1, st + s[i], n, m)
		func(0, 0, '', n, m)
		kk = list(set(res))
		return sorted(kk)


class Solution:

	def all_longest_common_subsequences(self, text1, text2):
		s1 = len(text1)
		s2 = len(text2)
		dp = [[0] * (s2 + 1) for i in range(s1 + 1)]
		for i in range(s1 + 1):
			dp[i][0] = 0
		for j in range(s2 + 1):
			dp[0][j] = 0
		for i in range(1, s1 + 1):
			for j in range(1, s2 + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

		def process(s1, s2, ind1, ind2, lcslen, curlcs, res, x, y):
			if len(curlcs) == lcslen:
				res.append(curlcs)
				return
			if ind1 >= x or ind2 >= y:
				return
			for i in range(ind1, x, 1):
				for j in range(ind2, y, 1):
					if s1[i] == s2[j]:
						process(s1, s2, i + 1, j + 1, lcslen, curlcs + s1[i], res, x, y)
		ind = dp[s1][s2]
		res = []
		process(text1, text2, 0, 0, dp[s1][s2], '', res, s1, s2)
		res = list(set(res))
		res.sort()
		return res


class Solution:

	def printLCS(self, i, j, s1, s2, res, cur_lcs, len_lcs, n1, n2):
		if len(cur_lcs) == len_lcs:
			res.append(cur_lcs)
			return
		if i >= n1 or j >= n2:
			return
		for k in range(i, n1):
			for p in range(j, n2):
				if s1[k] == s2[p]:
					self.printLCS(k + 1, p + 1, s1, s2, res, cur_lcs + s1[k], len_lcs, n1, n2)

	def all_longest_common_subsequences(self, s1, s2):
		len_lcs = 0
		n1 = len(s1)
		n2 = len(s2)
		dp = [[0 for i in range(n2 + 1)] for j in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		len_lcs = dp[n1][n2]
		if len_lcs == 0:
			return []
		res = []
		self.printLCS(0, 0, s1, s2, res, '', len_lcs, n1, n2)
		res = list(set(res))
		res.sort()
		return res


class Solution:

	def printlcs(self, ans, dp, i, j, s, t, l, x=''):
		if len(x) == l:
			ans.append(x)
		if i < 0 or j < 0:
			return
		for c in range(ord('a'), ord('z') + 1):
			char = chr(c)
			done = False
			for indx1 in range(i, -1, -1):
				if s[indx1] == char:
					for indx2 in range(j, -1, -1):
						if t[indx2] == char and dp[indx1][indx2] == l - len(x):
							self.printlcs(ans, dp, indx1 - 1, indx2 - 1, s, t, l, char + x)
							done = True
						if done:
							break
				if done:
					break

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0 for _ in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0:
					if s[i] == t[j]:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i][j - 1] if j >= 1 else dp[i - 1][j]
				elif s[i] == t[j]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		ans = []
		self.printlcs(ans, dp, n - 1, m - 1, s, t, dp[n - 1][m - 1])
		ans.sort()
		return ans


class Solution:

	def all_longest_common_subsequences(self, s, t):
		dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
		for i in range(1, len(s) + 1):
			for j in range(1, len(t) + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		n = len(s)
		m = len(t)
		lcslen = dp[len(s)][len(t)]
		ans = []

		def helper(ind1, ind2, curlcs):
			if len(curlcs) == lcslen:
				ans.append(curlcs)
				return
			if ind1 >= n or ind2 >= m:
				return
			for i in range(ind1, n):
				for j in range(ind2, m):
					if s[i] == t[j]:
						helper(i + 1, j + 1, curlcs + s[i])
		helper(0, 0, '')
		ans = list(set(ans))
		ans.sort()
		return ans


class Solution:

	def all_longest_common_subsequences(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

		def f(i, j, temp, lcs, ans, v):
			if len(temp) == lcs:
				ans.add(temp[::-1])
				return
			if i == 0 or j == 0:
				return
			for ii in range(i, 0, -1):
				for jj in range(j, 0, -1):
					if s[ii - 1] == t[jj - 1]:
						f(ii - 1, jj - 1, temp + s[ii - 1], lcs, ans, v)
		ans = set()
		v = set()
		f(n, m, '', dp[n][m], ans, v)
		return sorted(ans)


class Solution:

	def all_longest_common_subsequences(self, s, t):
		if len(s) < len(t):
			(s, t) = (t, s)
		dp = [[0 for _ in range(len(s))] for i in range(len(t))]
		for i in range(len(s)):
			if s[i] == t[0]:
				dp[0] = dp[0][:i] + [1 for _ in range(i, len(s))]
				break
		for i in range(1, len(t)):
			for j in range(len(s)):
				if not j:
					if t[i] == s[j]:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i - 1][j]
				elif t[i] == s[j]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = []
		visited = set()

		def recurse(i, j, st):
			visited.add((i, j, st))
			if dp[i][j] == 1 and s[j] == t[i]:
				lcs.append(s[j] + st)
			else:
				if s[j] == t[i] and (i - 1, j - 1) and ((i - 1, j - 1, s[j] + st) not in visited):
					recurse(i - 1, j - 1, s[j] + st)
				if dp[i - 1][j] == dp[i][j] and i and ((i - 1, j, st) not in visited):
					recurse(i - 1, j, st)
				if dp[i][j - 1] == dp[i][j] and j and ((i, j - 1, st) not in visited):
					recurse(i, j - 1, st)
		recurse(len(t) - 1, len(s) - 1, '')
		return sorted(list(set(lcs)))


class Solution:

	def all_longest_common_subsequences(self, s, t):
		(len_s, len_t) = (len(s), len(t))
		dp = [[0 for i in range(len_t + 1)] for j in range(len_s + 1)]
		for i in range(1, len_s + 1):
			for j in range(1, len_t + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = dp[-1][-1]
		ans = set()

		def checklgst(s, t, lcs, x=0, y=0, stg=''):
			if len(stg) == lcs:
				ans.add(stg)
				return
			if x >= len(s) or y >= len(t):
				return
			for i in range(x, len(s)):
				for j in range(y, len(t)):
					if s[i] == t[j]:
						checklgst(s, t, lcs, i + 1, j + 1, stg + s[i])
		checklgst(s, t, lcs)
		return sorted(ans)
		return sorted(ans)


class Solution:

	def all_longest_common_subsequences(self, s, t):
		memo = {}

		def dp(i, j):
			if (i, j) in memo.keys():
				return memo[i, j]
			if i < 0 or j < 0:
				return []
			arr = []
			if s[i] == t[j]:
				x = dp(i - 1, j - 1)
				if len(x):
					for ele in x:
						arr.append(ele + s[i])
				else:
					arr.append(s[i])
			else:
				arr += dp(i, j - 1)
				arr += dp(i - 1, j)
			mi = -1
			for ele in arr:
				mi = max(mi, len(ele))
			new = []
			for ele in arr:
				if len(ele) == mi:
					new.append(ele)
			memo[i, j] = new
			return list(set(new))
		return sorted(dp(len(s) - 1, len(t) - 1), key=str.lower)


import functools

class Solution:

	def all_longest_common_subsequences(self, s, t):
		x = len(s)
		y = len(t)
		dp = [[-1 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for ind1 in range(1, x + 1, 1):
			for ind2 in range(1, y + 1, 1):
				if s[ind1 - 1] == t[ind2 - 1]:
					dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
				else:
					dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
		res = []
		self.process(s, t, 0, 0, dp[x][y], [], res, x, y)
		fans = list(set(res))
		fans.sort()
		return fans

	def process(self, s1, s2, ind1, ind2, lcslen, lcstemp, res, x, y):
		if lcslen == 0:
			str1 = ''.join(lcstemp)
			res.append(str1)
			return
		if ind1 >= x or ind2 >= y:
			return
		for i in range(ind1, x, 1):
			for j in range(ind2, y, 1):
				if s1[i] == s2[j]:
					lcstemp.append(s1[i])
					self.process(s1, s2, i + 1, j + 1, lcslen - 1, lcstemp, res, x, y)
					lcstemp.pop(-1)


class Solution:

	def all_longest_common_subsequences(self, s, t):
		MAX = 100
		dp = [[-1 for i in range(MAX)] for i in range(MAX)]

		def lcs(str1, str2, len1, len2, i, j):
			if i == len1 or j == len2:
				dp[i][j] = 0
				return dp[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			ret = 0
			if str1[i] == str2[j]:
				ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1)
			else:
				ret = max(lcs(str1, str2, len1, len2, i + 1, j), lcs(str1, str2, len1, len2, i, j + 1))
			dp[i][j] = ret
			return ret

		def printAll(str1, str2, len1, len2, cur, indx1, indx2, currlcs, lcslen):
			if currlcs == lcslen:
				ans.append(cur)
				return
			if indx1 == len1 or indx2 == len2:
				return
			for ch in range(ord('a'), ord('z') + 1):
				done = False
				for i in range(indx1, len1):
					if chr(ch) == str1[i]:
						for j in range(indx2, len2):
							if chr(ch) == str2[j] and dp[i][j] == lcslen - currlcs:
								new_cur = cur + chr(ch)
								printAll(str1, str2, len1, len2, new_cur, i + 1, j + 1, currlcs + 1, lcslen)
								done = True
								break
							if done:
								break
		(len1, len2) = (len(s), len(t))
		lcslen = lcs(s, t, len1, len2, 0, 0)
		global ans
		ans = []
		printAll(s, t, len1, len2, '', 0, 0, 0, lcslen)
		ans.sort()
		w = set()
		pre = []
		for i in ans:
			if i in w:
				continue
			else:
				pre.append(i)
				w.add(i)
		return pre
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, t) = input().split()
		ob = Solution()
		ans = ob.all_longest_common_subsequences(s, t)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def all_longest_common_subsequences(self, s, t):
		memo = {}

		def dp(i, j):
			if (i, j) in memo.keys():
				return memo[i, j]
			if i < 0 or j < 0:
				return []
			arr = []
			if s[i] == t[j]:
				x = dp(i - 1, j - 1)
				if len(x):
					for ele in x:
						arr.append(ele + s[i])
				else:
					arr.append(s[i])
				arr = arr + dp(i - 1, j)
				arr = arr + dp(i, j - 1)
			else:
				arr += dp(i - 1, j - 1)
				arr += dp(i, j - 1)
				arr += dp(i - 1, j)
			mi = -1
			for ele in arr:
				mi = max(mi, len(ele))
			new = []
			for ele in arr:
				if len(ele) == mi:
					new.append(ele)
			memo[i, j] = new
			return list(set(new))
		return sorted(dp(len(s) - 1, len(t) - 1), key=str.lower)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, t) = input().split()
		ob = Solution()
		ans = ob.all_longest_common_subsequences(s, t)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def all_longest_common_subsequences(self, s, t):
		import sys
		dp = {}
		import functools

		@functools.lru_cache(None)
		def dfs(i, j):
			if i >= len(s) or j >= len(t):
				return 0
			if s[i] == t[j]:
				y1 = dfs(i + 1, j + 1) + 1
				return y1
			else:
				y1 = dfs(i + 1, j)
				y2 = dfs(i, j + 1)
				return max(y1, y2)
		x = dfs(0, 0)
		res = []

		@functools.lru_cache(None)
		def dfs2(i, j, str1):
			if i >= len(s) or j >= len(t):
				if len(str1) == x:
					res.append(str1)
				return 0
			if s[i] == t[j]:
				y1 = dfs2(i + 1, j + 1, str1 + s[i]) + 1
				y2 = dfs2(i + 1, j + 1, str1 + t[j]) + 1
				return max(y1, y2)
			else:
				y1 = dfs2(i + 1, j, str1)
				y2 = dfs2(i, j + 1, str1)
				return max(y1, y2)
		dfs2(0, 0, '')
		y = list(set(res))
		y.sort()
		return y


class Solution:

	def all_longest_common_subsequences(self, s, t):
		ns = len(s)
		nt = len(t)
		dp = [[0 for _ in range(nt + 1)] for _ in range(ns + 1)]
		ans = [[set() for _ in range(nt + 1)] for _ in range(ns + 1)]
		for i in range(1, ns + 1):
			for j in range(1, nt + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if not ans[i - 1][j - 1]:
						ans[i][j].add(s[i - 1])
					else:
						for xx in ans[i - 1][j - 1]:
							ans[i][j].add(xx + s[i - 1])
				else:
					dp[i][j] = dp[i - 1][j]
					for xx in ans[i - 1][j]:
						ans[i][j].add(xx)
					if dp[i][j] < dp[i][j - 1]:
						dp[i][j] = dp[i][j - 1]
						ans[i][j] = ans[i][j - 1]
					elif dp[i][j] == dp[i][j - 1]:
						for xx in ans[i][j - 1]:
							ans[i][j].add(xx)
		return sorted(ans[-1][-1])


class Solution:

	def check(self, res, s, t, x, y, l, arr):
		if len(res) == l:
			arr.add(res)
			return
		if x == len(s) or y == len(t):
			return
		for i in range(97, 123):
			for j in range(x, len(s)):
				if s[j] == chr(i):
					for k in range(y, len(t)):
						if t[k] == chr(i):
							self.check(res + chr(i), s, t, j + 1, k + 1, l, arr)

	def all_longest_common_subsequences(self, s, t):
		dp = []
		for i in range(len(s) + 1):
			x = []
			for j in range(len(t) + 1):
				x.append(0)
			dp.append(x)
		for i in range(1, len(s) + 1):
			for j in range(1, len(t) + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		l = dp[len(s)][len(t)]
		arr = set()
		self.check('', s, t, 0, 0, l, arr)
		arr = list(arr)
		arr.sort()
		return arr


class Solution:

	def __init__(self):
		self.output = []

	def solve(self, s1, s2, i, j, ans, lcs):
		if lcs == 0:
			x = ''.join(ans)
			if x not in self.output:
				self.output.append(x)
			return
		for r in range(i, len(s1)):
			for c in range(j, len(s2)):
				if s1[r] == s2[c]:
					ans.append(s1[r])
					self.solve(s1, s2, r + 1, c + 1, ans, lcs - 1)
					ans.pop()
		return

	def all_longest_common_subsequences(self, s1, s2):
		x = len(s1)
		y = len(s2)
		table = [[0 for i in range(y + 1)] for j in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					table[i][j] = 1 + table[i - 1][j - 1]
				else:
					table[i][j] = max(table[i - 1][j], table[i][j - 1])
		i = 0
		j = 0
		ans = []
		self.solve(s1, s2, i, j, ans, table[x][y])
		self.output.sort()
		return self.output


class Solution:

	def all_longest_common_subsequences(self, x, y):
		MAX = 100
		dp = [[-1 for i in range(MAX)] for i in range(MAX)]

		def lcs(str1, str2, len1, len2, i, j):
			if i == len1 or j == len2:
				dp[i][j] = 0
				return dp[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			ret = 0
			if str1[i] == str2[j]:
				ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1)
			else:
				ret = max(lcs(str1, str2, len1, len2, i + 1, j), lcs(str1, str2, len1, len2, i, j + 1))
			dp[i][j] = ret
			return ret

		def printAll(str1, str2, len1, len2, cur, indx1, indx2, currlcs, lcslen):
			if currlcs == lcslen:
				ans.append(cur)
				return
			if indx1 == len1 or indx2 == len2:
				return
			for ch in range(ord('a'), ord('z') + 1):
				done = False
				for i in range(indx1, len1):
					if chr(ch) == str1[i]:
						for j in range(indx2, len2):
							if chr(ch) == str2[j] and dp[i][j] == lcslen - currlcs:
								new_cur = cur + chr(ch)
								printAll(str1, str2, len1, len2, new_cur, i + 1, j + 1, currlcs + 1, lcslen)
								done = True
								break
							if done:
								break
		(len1, len2) = (len(s), len(t))
		lcslen = lcs(s, t, len1, len2, 0, 0)
		global ans
		ans = []
		printAll(s, t, len1, len2, '', 0, 0, 0, lcslen)
		ans.sort()
		w = set()
		pre = []
		for i in ans:
			if i in w:
				continue
			else:
				pre.append(i)
				w.add(i)
		return pre


class Solution:

	def printLcs(self, ind1, ind2, dp, cur, length, data, ans, s, t):
		if cur == length:
			ans.append(''.join(data[:cur]))
		if ind1 == len(s) or ind2 == len(t):
			return
		for ch in range(ord('a'), ord('z') + 1):
			done = False
			for i in range(ind1, len(s)):
				if chr(ch) == s[i]:
					for j in range(ind2, len(t)):
						if t[j] == chr(ch) and dp[i][j] == cur:
							data[cur] = chr(ch)
							self.printLcs(i + 1, j + 1, dp, cur + 1, length, data, ans, s, t)
							done = True
							break
				if done:
					break

	def lcs(self, s, t, dp):
		for i in range(1, len(s) + 1):
			for j in range(1, len(t) + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]

	def all_longest_common_subsequences(self, s, t):
		dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]
		lcsLength = self.lcs(s, t, dp)
		ans = []
		data = ['a' for i in range(100)]
		self.printLcs(0, 0, dp, 0, lcsLength, data, ans, s, t)
		return ans


from collections import deque
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def all_longest_common_subsequences(self, text1, text2):
		ans = 0
		m = len(text1)
		n = len(text2)
		dp = [[0] * (len(text1) + 1) for i in range(len(text2) + 1)]
		vis = [[0] * (len(text1) + 1) for i in range(len(text2) + 1)]
		for i in range(1, len(text2) + 1):
			for j in range(1, len(text1) + 1):
				if text2[i - 1] == text1[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		memo = defaultdict(list)
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if text1[j - 1] == text2[i - 1]:
					for k in memo[i - 1, j - 1]:
						memo[i, j].append(k + text1[j - 1])
					if memo[i, j] == []:
						memo[i, j].append(text1[j - 1])
				else:
					maxi = max(dp[i - 1][j], dp[i][j - 1])
					if maxi == dp[i - 1][j]:
						memo[i, j] += memo[i - 1, j]
					if maxi == dp[i][j - 1]:
						memo[i, j] += memo[i, j - 1]
				memo[i, j] = list(set(memo[i, j]))
			if i > 1:
				for j in range(1, m + 1):
					if (i - 2, j) in memo:
						memo.pop((i - 2, j))
		ans = sorted(memo[n, m])
		return ans


class Solution:

	def all_longest_common_subsequences(self, text1, text2):
		m = len(text1)
		n = len(text2)
		dp1 = [set(['']) for i in range(m + 1)]
		for i in range(n):
			dp2 = [set() for t in range(m + 1)]
			dp2[0].add('')
			for j in range(m):
				if text1[j] == text2[i]:
					for t in dp1[j]:
						dp2[j + 1].add(t + text1[j])
				else:
					maxi = max(len(next(iter(dp2[j]))), len(next(iter(dp1[j + 1]))))
					if maxi == len(next(iter(dp2[j]))):
						for t in dp2[j]:
							dp2[j + 1].add(t)
					if maxi == len(next(iter(dp1[j + 1]))):
						for t in dp1[j + 1]:
							dp2[j + 1].add(t)
			dp1 = dp2
		return sorted(list(dp2[-1]))


class Solution:

	def all_longest_common_subsequences(self, s, t):
		temp2 = []
		for j in range(len(t) + 1):
			temp1 = []
			for i in range(len(s) + 1):
				temp1.append([0, []])
			temp2.append(temp1)
		for i in range(1, len(t) + 1):
			for j in range(1, len(s) + 1):
				if t[i - 1] == s[j - 1]:
					temp3 = temp2[i - 1][j - 1][0] + 1
					temp4 = []
					if len(temp2[i - 1][j - 1][1]) == 0:
						temp4.append(t[i - 1])
					else:
						for k in temp2[i - 1][j - 1][1]:
							temp4 = temp4 + [k + t[i - 1]]
				else:
					temp3 = max(temp2[i - 1][j][0], temp2[i][j - 1][0])
					temp4 = []
					if temp3 == temp2[i - 1][j][0]:
						if len(temp2[i - 1][j][1]) != 0:
							for k in temp2[i - 1][j][1]:
								temp4 = temp4 + [k]
					if temp3 == temp2[i][j - 1][0]:
						if len(temp2[i][j - 1][1]) != 0:
							for k in temp2[i][j - 1][1]:
								temp4 = temp4 + [k]
				temp2[i][j][0] = temp3
				temp2[i][j][1] = set(temp4)
		result = list(temp2[len(t)][len(s)][1])
		result.sort()
		return result


class Solution:

	def all_longest_common_subsequences(self, s, t):
		(n, m) = (len(s), len(t))
		dp = [[[0, set()] for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(n):
			dp[i][0][1].add('')
		for i in range(m):
			dp[0][i][1].add('')
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j][0] = dp[i - 1][j - 1][0] + 1
					for string in dp[i - 1][j - 1][1]:
						dp[i][j][1].add(string + s[i - 1])
				else:
					if dp[i - 1][j][0] >= dp[i][j - 1][0]:
						dp[i][j][0] = dp[i - 1][j][0]
						dp[i][j][1] |= dp[i - 1][j][1]
					if dp[i][j - 1][0] >= dp[i - 1][j][0]:
						dp[i][j][0] = dp[i][j - 1][0]
						dp[i][j][1] |= dp[i][j - 1][1]
		return sorted(dp[n][m][1])


class Solution:

	def all_longest_common_subsequences(self, s, t):
		(x, y) = (len(s), len(t))
		dp = [[[0, {''}] if i == 0 or j == 0 else [0, set()] for j in range(y + 1)] for i in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s[i - 1] == t[j - 1]:
					for tmp in dp[i - 1][j - 1][1]:
						dp[i][j][1].add(tmp + s[i - 1])
					dp[i][j][0] = dp[i - 1][j - 1][0] + 1
				elif dp[i - 1][j][0] > dp[i][j - 1][0]:
					dp[i][j] = [dp[i - 1][j][0], dp[i - 1][j][1].copy()]
				elif dp[i - 1][j][0] < dp[i][j - 1][0]:
					dp[i][j] = [dp[i][j - 1][0], dp[i][j - 1][1].copy()]
				else:
					dp[i][j] = [dp[i - 1][j][0], dp[i - 1][j][1].union(dp[i][j - 1][1])]
		return sorted(list(dp[x][y][1]))