In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. A substring of a string is a continuous subsequence of the string. For example, BCD is a substring of ABCDEF.

You are given two strings s_1, s_2 and another string called virus. Your task is to find the longest common subsequence of s_1 and s_2, such that it doesn't contain virus as a substring.


-----Input-----

The input contains three strings in three separate lines: s_1, s_2 and virus (1 ≤ |s_1|, |s_2|, |virus| ≤ 100). Each string consists only of uppercase English letters.


-----Output-----

Output the longest common subsequence of s_1 and s_2 without virus as a substring. If there are multiple answers, any of them will be accepted. 

If there is no valid common subsequence, output 0.


-----Examples-----
Input
AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ

Output
ORZ

Input
AA
A
A

Output
0

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Dynamic programming


Solutions:
(s1, s2, virus) = [input().strip() for _ in range(3)]
(n, m, v) = (len(s1), len(s2), len(virus))
next_suffix = [v for i in range(v)]
for i in range(v - 2, -1, -1):
	j = next_suffix[i + 1]
	while j <= v - 1 and virus[j] != virus[i + 1]:
		j = next_suffix[j]
	next_suffix[i] = j - 1

def memoize(function):
	memo = dict()

	def memoized(*args):
		if args in memo:
			return memo[args]
		ans = function(*args)
		memo[args] = ans
		return ans
	return memoized

@memoize
def lcs(i, j, k):
	if k < 0:
		return (float('-inf'), '')
	if i < 0 or j < 0:
		return (0, '')
	if s1[i] == s2[j]:
		if s1[i] != virus[k]:
			newk = k
			while newk < v and virus[newk] != s1[i]:
				newk = next_suffix[newk]
			r = lcs(i - 1, j - 1, newk - 1)
			return (r[0] + 1, r[1] + s1[i])
		else:
			r1 = lcs(i - 1, j - 1, k - 1)
			r1 = (r1[0] + 1, r1[1] + s1[i])
			r2 = lcs(i - 1, j - 1, k)
			return max(r1, r2, key=lambda x: x[0])
	return max(lcs(i, j - 1, k), lcs(i - 1, j, k), key=lambda x: x[0])
ans = lcs(n - 1, m - 1, v - 1)
if ans[0] > 0:
	print(ans[1])
else:
	print(0)


A = input()
B = input()
virus = input()
piTable = [0] * len(virus)
j = 0
for i in range(1, len(virus)):
	while virus[i] != virus[j] and j != 0:
		j = piTable[j - 1]
	if virus[i] == virus[j]:
		piTable[i] = j + 1
		j += 1
	else:
		piTable[i] = 0
memo = {}
parent = {}

def dp(i, j, k):
	if k == len(virus):
		return -10000
	if i == len(A):
		return 0
	if j == len(B):
		return 0
	if (i, j, k) in memo:
		return memo[i, j, k]
	choices = [dp(i + 1, j, k), dp(i, j + 1, k)]
	new_k = k
	if A[i] == B[j]:
		if A[i] == virus[k]:
			choices.append(dp(i + 1, j + 1, k + 1) + 1)
			new_k = k + 1
		else:
			while A[i] != virus[new_k] and new_k != 0:
				new_k = piTable[new_k - 1]
			if A[i] == virus[new_k]:
				new_k += 1
				choices.append(dp(i + 1, j + 1, new_k) + 1)
			else:
				choices.append(dp(i + 1, j + 1, 0) + 1)
	memo[i, j, k] = max(choices)
	index = choices.index(memo[i, j, k])
	if index == 0:
		parent[i, j, k] = (i + 1, j, k)
	elif index == 1:
		parent[i, j, k] = (i, j + 1, k)
	else:
		parent[i, j, k] = (i + 1, j + 1, new_k)
	return memo[i, j, k]
max_size_subsequence = dp(0, 0, 0)
if max_size_subsequence == 0:
	print(0)
else:
	ANSWER = ''
	current_state = (0, 0, 0)
	next_state = None
	while current_state != None:
		next_state = parent[current_state] if current_state in parent else None
		if next_state is None:
			break
		if next_state[0] == current_state[0] + 1 and next_state[1] == current_state[1] + 1:
			ANSWER += A[current_state[0]]
		current_state = next_state
	print(ANSWER)


(a, b, v) = (input(), input(), input())
t = [[-1] * len(b) for x in range(len(a))]

def g(i, j):
	if i < 0 or j < 0:
		return ''
	if t[i][j] == -1:
		s = g(i - 1, j - 1)
		if a[i] == b[j]:
			s += a[i]
		t[i][j] = max(s, g(i - 1, j), g(i, j - 1), key=lambda q: len(q) - q.count(v))
	return t[i][j]
s = g(len(a) - 1, len(b) - 1)
while v in s:
	s = min(s.replace(v, v[:-1]), s.replace(v, v[1:]), key=lambda q: q.count(v))
print(s if s else 0)


from functools import reduce
a = input()
b = input()
c = input()
alen = len(a)
blen = len(b)
clen = len(c)
kmpnext = [0] * (clen + 1)
i = 1
j = 0
while i < clen:
	while j > 0 and c[i] != c[j]:
		j = kmpnext[j]
	if c[i] == c[j]:
		j += 1
	kmpnext[i + 1] = j
	i += 1
f = [[[0 for i in range(clen + 2)] for i in range(blen + 2)] for i in range(alen + 2)]
g = [[[0 for i in range(clen + 2)] for i in range(blen + 2)] for i in range(alen + 2)]
h = [[[0 for i in range(clen + 2)] for i in range(blen + 2)] for i in range(alen + 2)]
f[0][0][0] = 0
g[0][0][0] = (-1, -1, -1)
h[0][0][0] = 1
m = (0, 0, 0)
for i in range(alen):
	for j in range(blen):
		for k in range(clen):
			if h[i][j][k] == 0:
				continue
			if f[i + 1][j][k] < f[i][j][k] or h[i + 1][j][0] == 0:
				f[i + 1][j][k] = f[i][j][k]
				g[i + 1][j][k] = g[i][j][k]
				h[i + 1][j][k] = 1
			if f[i][j + 1][k] < f[i][j][k] or h[i][j + 1][0] == 0:
				f[i][j + 1][k] = f[i][j][k]
				g[i][j + 1][k] = g[i][j][k]
				h[i][j + 1][k] = 1
			if a[i] == b[j]:
				kt = k
				while kt != 0 and a[i] != c[kt]:
					kt = kmpnext[kt]
				if a[i] == c[kt]:
					if f[i + 1][j + 1][kt + 1] < f[i][j][k] + 1:
						f[i + 1][j + 1][kt + 1] = f[i][j][k] + 1
						g[i + 1][j + 1][kt + 1] = (i, j, k)
						h[i + 1][j + 1][kt + 1] = 1
				elif f[i + 1][j + 1][0] < f[i][j][k] + 1:
					f[i + 1][j + 1][0] = f[i][j][k] + 1
					g[i + 1][j + 1][0] = (i, j, k)
					h[i + 1][j + 1][0] = 1
for i in range(alen + 1):
	for j in range(blen + 1):
		for k in range(clen):
			if f[i][j][k] > f[m[0]][m[1]][m[2]]:
				m = (i, j, k)
if f[m[0]][m[1]][m[2]] == 0:
	print(0)
else:
	ans = ''
	t = m
	t = g[t[0]][t[1]][t[2]]
	while t != (-1, -1, -1):
		ans = a[t[0]] + ans
		t = g[t[0]][t[1]][t[2]]
	print(ans)


def gen(i, j):
	if a[i][j] == -1:
		a[i][j] = max(gen(i - 1, j - 1) + s2[i - 1] * (s2[i - 1] == s1[j - 1]), gen(i - 1, j), gen(i, j - 1), key=lambda x: [len(x), -x.count(viru)])
	return a[i][j]
(s1, s2, viru) = [input() for x in range(3)]
a = [[''] * (len(s1) + 1)] + [[''] + [-1] * len(s1) for x in range(len(s2))]
ans = gen(len(s2), len(s1))
while viru in ans:
	ans = min(ans.replace(viru, viru[:-1]), ans.replace(viru, viru[1:]), key=lambda x: x.count(viru))
print(ans + '0' * (ans == ''))


def Solve(x, y, c):
	if c == len(virus):
		return 0
	if x == len(s1) or y == len(s2):
		return ''
	if (x, y, c) in Mem:
		return Mem[x, y, c]
	ans = ''
	if s1[x] == s2[y]:
		q = 0
		if s1[x] == virus[c]:
			q = Solve(x + 1, y + 1, c + 1)
			if q != 0:
				q = s1[x] + q
		else:
			done = False
			for match in T[c]:
				if s1[x] == virus[match]:
					done = True
					q = Solve(x + 1, y + 1, match + 1)
					if q != 0:
						q = s1[x] + q
					break
			if not done:
				q = Solve(x + 1, y + 1, 0)
				if q != 0:
					q = s1[x] + q
		if q != 0:
			ans = q
	q = Solve(x + 1, y, c)
	if q != 0:
		ans = max(ans, Solve(x + 1, y, c), key=len)
	q = Solve(x, y + 1, c)
	if q != 0:
		ans = max(ans, Solve(x, y + 1, c), key=len)
	Mem[x, y, c] = ans
	return ans
Mem = {}
s1 = input()
s2 = input()
virus = input()
T = [0] * len(virus)
T[0] = [0]
for i in range(1, len(virus)):
	done = False
	T[i] = []
	for j in range(1, i):
		if virus[j:i] == virus[:i - j]:
			T[i].append(i - j)
	T[i].append(0)
e = Solve(0, 0, 0)
if e == '':
	print(0)
else:
	print(Solve(0, 0, 0))


(a, b, s) = (input(), input(), input())
i = 0
p = [-1] + [0] * len(s)
for j in range(1, len(s)):
	while i + 1 and s[i] != s[j]:
		i = p[i]
	i += 1
	p[j + 1] = i
f = lambda a, b: a if len(a) > len(b) else b
g = lambda : [[''] * len(s) for i in range(len(b) + 1)]
(u, v) = (g(), g())
for x in a:
	for (i, y) in enumerate(b):
		v[i] = [f(x, y) for (x, y) in zip(u[i], v[i - 1])]
		if x == y:
			for (k, n) in enumerate(u[i - 1]):
				while k > -1 and x != s[k]:
					k = p[k]
				k += 1
				if k < len(s):
					v[i][k] = f(v[i][k], n + x)
	(u, v) = (v, g())
t = max(u[-2], key=lambda q: len(q))
print(t if t else 0)


s = input()
t = input()
u = input()
memos = {}

def solve(a, b, c):
	if c == len(u):
		return 0
	if a == len(s) or b == len(t):
		return ''
	if (a, b, c) in memos:
		return memos[a, b, c]
	me = s[a]
	r = solve(a + 1, b, c)
	try:
		idx = t[b:].index(me)
		curr = u[:c] + me
		for i in range(c + 2):
			if curr[i:] == u[:c + 1 - i]:
				tr = solve(a + 1, b + idx + 1, c + 1 - i)
				if tr == 0:
					r2 = 0
				else:
					r2 = me + tr
				break
		if r2 == 0 or len(r) > len(r2):
			k = r
		else:
			k = r2
	except ValueError:
		k = r
	memos[a, b, c] = k
	return k
aaa = solve(0, 0, 0)
if aaa == '':
	print(0)
else:
	print(aaa)


(a, b, v) = (input(), input(), input())
h = [[-1] * len(b) for i in range(len(a))]

def f(ab):
	return ab.count(v)

def g(i, j):
	if i < 0 or j < 0:
		return ''
	if h[i][j] == -1:
		s = g(i - 1, j - 1)
		if a[i] == b[j]:
			s += a[i]
		s1 = g(i - 1, j)
		s2 = g(i, j - 1)
		if len(s1) - f(s1) > len(s) - f(s):
			s = s1
		if len(s2) - f(s2) > len(s) - f(s):
			s = s2
		h[i][j] = s
	return h[i][j]
ss = g(len(a) - 1, len(b) - 1)
while v in ss:
	ss1 = ss.replace(v, v[:-1])
	ss2 = ss.replace(v, v[1:])
	if f(ss1) < f(ss2):
		ss = ss1
	else:
		ss = ss2
if len(ss) > 0:
	print(ss)
else:
	print(0)


def dfs(i, j):
	if a[i][j] != -1:
		return a[i][j]
	d1 = dfs(i - 1, j - 1) + (s1[i - 1] == s2[j - 1]) * s1[i - 1]
	d2 = dfs(i - 1, j)
	d3 = dfs(i, j - 1)
	a[i][j] = max(d1, d2, d3, key=lambda x: [len(x), -x.count(virus)])
	return a[i][j]
(s1, s2, virus) = (input(), input(), input())
(n1, n2) = (len(s1), len(s2))
a = [[''] * (n2 + 1)] + [[''] + [-1] * n2 for i in range(n1)]
ans = dfs(n1, n2)
while virus in ans:
	ans = min(ans.replace(virus, virus[:-1]), ans.replace(virus, virus[1:]), key=lambda x: x.count(virus))
print(0 if ans == '' else ans)


s = '/' + input()
s1 = '/' + input()
virus = input()
d = dict()
aux = ''
for i in range(len(virus)):
	for j in range(65, 91):
		aux1 = aux + chr(j)
		y = 0
		for k in range(i + 1):
			if aux1[0 + k:i + 1] == virus[0:i + 1 - k]:
				y = i + 1 - k
				break
		d.update({tuple([i, chr(j)]): y})
	aux += virus[i]
n = len(s)
m = len(s1)
dp = [[['' for k in range(len(virus) + 1)] for i in range(m + 1)] for j in range(n + 1)]
for i in range(1, n):
	for j in range(1, m):
		if s[i] == s1[j]:
			for k in range(len(virus)):
				y = d[k, s[i]]
				if y == len(virus):
					continue
				if len(dp[i - 1][j - 1][k]) + 1 > len(dp[i][j][y]) and len(dp[i - 1][j - 1][k]) + 1 > len(dp[i][j - 1][y]) and (len(dp[i - 1][j - 1][k]) + 1 > len(dp[i - 1][j][y])):
					dp[i][j][y] = dp[i - 1][j - 1][k] + s[i]
		for k in range(len(virus)):
			if len(dp[i - 1][j][k]) > len(dp[i][j - 1][k]) and len(dp[i - 1][j][k]) > len(dp[i][j][k]):
				dp[i][j][k] = dp[i - 1][j][k]
			elif len(dp[i][j - 1][k]) >= len(dp[i - 1][j][k]) and len(dp[i][j - 1][k]) > len(dp[i][j][k]):
				dp[i][j][k] = dp[i][j - 1][k]
ans = ''
for i in dp[n - 1][m - 1][0:len(virus)]:
	if len(i) > len(ans):
		ans = i
if len(ans) > 0:
	print(ans)
else:
	print(0)