You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a subsequence of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.

Subsequence of string s is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string s.


-----Input-----

The first line contains string a, and the second line — string b. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 10^5 characters.


-----Output-----

On the first line output a subsequence of string a, obtained from b by erasing the minimum number of consecutive characters.

If the answer consists of zero characters, output «-» (a minus sign).


-----Examples-----
Input
hi
bob

Output
-

Input
abca
accepted

Output
ac

Input
abacaba
abcdcba

Output
abcba



-----Note-----

In the first example strings a and b don't share any symbols, so the longest string that you can get is empty.

In the second example ac is a subsequence of a, and at the same time you can obtain it by erasing consecutive symbols cepted from string b.

Difficulty: HARD
Tags: String algorithms

Sorting

Amortized analysis
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
a = input()
b = input()
p = [None] * (len(b) + 1)
s = [None] * (len(b) + 1)
j = 0
p[0] = -1
for i in range(len(b)):
	while j < len(a) and a[j] != b[i]:
		j += 1
	if j >= len(a):
		break
	else:
		p[i + 1] = j
		j += 1
j = len(a) - 1
s[-1] = len(b)
for i in range(len(b) - 1, -1, -1):
	while j >= 0 and a[j] != b[i]:
		j -= 1
	if j < 0:
		break
	else:
		s[i] = j
		j -= 1
ans = ''
for i in range(len(b) + 1):
	if p[i] == None:
		break
	else:
		l = i - 1
		r = len(b)
		while l + 1 < r:
			mid = (l + r) // 2
			if s[mid] != None and p[i] < s[mid]:
				r = mid
			else:
				l = mid
		if len(ans) < i + len(b) - r:
			ans = b[:i] + b[r:]
if ans == '':
	print('-')
else:
	print(ans)


def get_substr_ends(haystack, needle):
	ans = [-1]
	index = 0
	for char in needle:
		while index < len(haystack) and char != haystack[index]:
			index += 1
		ans.append(index)
		if index < len(haystack):
			index += 1
	return ans
haystack = input()
needle = input()
pref = get_substr_ends(haystack, needle)
suff = get_substr_ends(haystack[::-1], needle[::-1])
pref_index = 0
suff_len = 0
while suff_len < len(suff) and suff[suff_len] < len(haystack):
	suff_len += 1
suff_len -= 1
best_str = needle[len(needle) - suff_len:]
if len(best_str) == len(needle):
	print(needle)
	exit(0)
for pref_len in range(1, len(pref)):
	while suff_len >= 0 and suff[suff_len] + pref[pref_len] + 2 > len(haystack):
		suff_len -= 1
	ans = pref_len + suff_len
	if ans > len(best_str) and suff_len >= 0:
		best_str = needle[:pref_len] + needle[len(needle) - suff_len:]
print(best_str if best_str else '-')


import math

def prefixIds(a, b):
	prefSubsId = [math.inf] * len(b)
	bId = 0
	aId = 0
	while aId < len(a):
		if bId == len(b):
			break
		if a[aId] == b[bId]:
			prefSubsId[bId] = aId + 1
			bId += 1
			aId += 1
		else:
			aId += 1
	return prefSubsId
a = input()
b = input()
n = len(b)
prefLens = prefixIds(a, b)
suffLens = prefixIds(a[::-1], b[::-1])[::-1]
prefLen = 0
suffLen = 0
minCutLen = n
lBorder = -1
rBorder = n
while suffLen < n and suffLens[suffLen] == math.inf:
	suffLen += 1
curCutLen = suffLen
if curCutLen < minCutLen:
	minCutLen = curCutLen
	rBorder = suffLen
while prefLen < suffLen and prefLens[prefLen] != math.inf:
	while suffLen < n and prefLens[prefLen] + suffLens[suffLen] > len(a):
		suffLen += 1
	curCutLen = suffLen - prefLen - 1
	if curCutLen < minCutLen:
		minCutLen = curCutLen
		lBorder = prefLen
		rBorder = suffLen
	prefLen += 1
if minCutLen == n:
	print('-')
elif minCutLen == 0:
	print(b)
else:
	print(b[:lBorder + 1] + b[rBorder:])


a = input()
b = input()
prefix = [-1] * len(b)
postfix = [-1] * len(b)
prefix[0] = a.find(b[0])
postfix[len(b) - 1] = a.rfind(b[len(b) - 1])
for i in range(1, len(b)):
	prefix[i] = a.find(b[i], prefix[i - 1] + 1)
	if prefix[i] == -1:
		break
for i in range(len(b) - 2, -1, -1):
	postfix[i] = a.rfind(b[i], 0, postfix[i + 1])
	if postfix[i] == -1:
		break
best_left = -1
best_right = len(b)
left = -1
while left + 1 < len(b) and prefix[left + 1] != -1:
	left += 1
if left > -1:
	best_left = left
	best_right = len(b)
right = len(b)
while right - 1 >= 0 and postfix[right - 1] != -1:
	right -= 1
if right < len(b) and right + 1 < best_right - best_left:
	best_left = -1
	best_right = right
left = 0
right = len(b)
while left < right and postfix[right - 1] != -1 and (postfix[right - 1] > prefix[left]):
	right -= 1
while prefix[left] != -1 and left < right < len(b):
	while right < len(b) and postfix[right] <= prefix[left]:
		right += 1
	if right >= len(b):
		break
	if right - left < best_right - best_left:
		best_left = left
		best_right = right
	left += 1
	if left == right:
		right += 1
res = b[:best_left + 1] + b[best_right:]
if res == '':
	print('-')
else:
	print(res)


(a, b) = (input(), input())
n = len(b)

def f(a, b):
	(i, t) = (0, [0])
	for q in a:
		if i < n and q == b[i]:
			i += 1
		t.append(i)
	return t
(u, v) = (f(a, b), f(a[::-1], b[::-1])[::-1])
t = [x + y for (x, y) in zip(u, v)]
i = t.index(max(t))
(x, y) = (u[i], v[i])
s = b[:x] + b[max(x, n - y):]
print(s if s else '-')


a = list(input())
b = list(input())
m = len(a)
n = len(b)
s = [-1]
i = 0
j = 0
while i < m and j < n:
	if a[i] == b[j]:
		s.append(i)
		j += 1
	i += 1
e = [1000000]
i = m - 1
j = n - 1
while i >= 0 and j >= 0:
	if a[i] == b[j]:
		e.append(i)
		j -= 1
	i -= 1
i = len(s) - 1
j = 0
ans = '-'
ctr = 0
while j < len(e) and i >= 0:
	if s[i] < e[j]:
		if i + j > ctr and i + j <= len(b):
			ctr = i + j
			if j > 0:
				ans = b[:i] + b[-j:]
			else:
				ans = b[:i]
		j += 1
	else:
		i -= 1
print(''.join(ans))


from macpath import curdir
import bisect
a = input()
b = input()
la = len(a)
lb = len(b)
forb = [la] * lb
cur = 0
for i in range(lb):
	while cur < la and a[cur] != b[i]:
		cur += 1
	if cur < la:
		forb[i] = cur
		cur += 1
	else:
		break
cur = la - 1
bacb = [-1] * lb
for i in range(lb - 1, -1, -1):
	while cur >= 0 and a[cur] != b[i]:
		cur -= 1
	if cur >= 0:
		bacb[i] = cur
		cur -= 1
	else:
		break
res = lb
start = 0
end = lb
for i in range(lb):
	low = -1
	if i > 0:
		low = forb[i - 1]
	if low >= la:
		break
	j = bisect.bisect_right(bacb, low)
	if res > j - i >= 0:
		res = j - i
		start = i
		end = j
if res == lb:
	print('-')
else:
	print(b[:start] + b[end:])


a = input()
b = input()
pre = [len(a) for i in range(len(b))]
suf = [-1 for i in range(len(b))]
temp = 0
whole = 0
for i in range(len(a)):
	if b[temp] == a[i]:
		pre[temp] = i
		temp += 1
		if temp == len(b):
			whole = 1
			break
temp = len(b) - 1
for i in range(len(a) - 1, -1, -1):
	if b[temp] == a[i]:
		suf[temp] = i
		temp -= 1
		if temp == -1:
			whole = 1
			break
ans = []
index = 0
for i in range(len(b)):
	temp = pre[i]
	index = max(i + 1, index)
	start = index
	for j in range(start, len(b)):
		if suf[j] > pre[i]:
			index = j
			break
	else:
		index = len(b)
	if index != len(b) and pre[i] != len(a):
		ans += [len(b) + 1 + i - index]
	elif pre[i] == len(a):
		ans += [0]
	elif index == len(b) and pre[i] != len(a):
		ans += [i + 1]
	else:
		ans += [0]
MAXsufANS = 0
MAXsufindex = len(b)
for i in range(len(b) - 1, -1, -1):
	if suf[i] != -1:
		MAXsufANS = len(b) - i
		MAXsufindex = i
MAX = 0
MAXindex = -1
for i in range(len(b)):
	if ans[i] > MAX:
		MAXindex = i
		MAX = ans[i]
usesuf = 0
if MAXsufANS > MAX:
	usesuf = 1
if whole == 1:
	print(b)
elif max(MAX, MAXsufANS) == 0:
	print('-')
elif usesuf == 1:
	anss = b[MAXsufindex:]
	print(anss)
else:
	m = MAXindex
	L = MAX
	anss = b[:m + 1] + b[len(b) - (MAX - (m + 1)):]
	print(anss)


import sys
input = sys.stdin.readline

def solve():
	a = input().strip()
	b = input().strip()
	n = len(a)
	m = len(b)
	c = [0] * m
	d = [0] * m
	p = 0
	for i in range(m):
		for j in range(p, n):
			if a[j] == b[i]:
				c[i] = j
				p = j + 1
				break
		else:
			for j in range(i, m):
				c[j] = n
			break
	p = n - 1
	for i in range(m - 1, -1, -1):
		for j in range(p, -1, -1):
			if a[j] == b[i]:
				d[i] = j
				p = j - 1
				break
		else:
			for j in range(i, -1, -1):
				d[j] = -1
			break
	j = 0
	while j < m and d[j] < 0:
		j += 1
	res = (m - j, 0, j)
	for i in range(m):
		p = c[i]
		if p == n:
			break
		while j < m and (j <= i or d[j] <= p):
			j += 1
		res = max(res, (i + 1 + m - j, i + 1, j))
	if res[0] == 0:
		print('-')
	else:
		print(b[:res[1]] + b[res[2]:])
solve()


(a, b) = (str(input()), str(input()))
(p, s, pp, sp) = ([0] * len(b), [0] * len(b), 0, len(a) - 1)
p[0] = a.find(b[0])
while sp >= 0 and a[sp] != b[-1]:
	sp -= 1
s[len(b) - 1] = sp
(pp, sp) = (p[0] + 1, sp - 1)
for i in range(1, len(b)):
	if p[i - 1] == -1:
		p[i] = -1
	else:
		while pp < len(a) and a[pp] != b[i]:
			pp += 1
		p[i] = pp if pp < len(a) else -1
		pp += 1
for i in range(len(b) - 2, -1, -1):
	if s[i + 1] == -1:
		s[i] = -1
	else:
		while sp >= 0 and a[sp] != b[i]:
			sp -= 1
		s[i] = sp if sp >= 0 else -1
		sp -= 1
(anss, ans) = (0, (-1, -1, -1))
for i in range(0, len(b)):
	if p[i] == -1:
		break
	while anss < len(b) and (s[anss] <= p[i] or s[anss] == -1) or anss <= i:
		anss += 1
	ln = (i + 1 if p[i] != -1 else 0) + (len(b) - anss if anss < len(b) and s[anss] != -1 else 0)
	if ln > ans[0]:
		ans = (ln, i, anss)
only_s = len(b) - 1
while only_s - 1 >= 0 and s[only_s - 1] >= 0:
	only_s -= 1
if only_s >= 0 and s[-1] >= 0 and (len(b) - only_s > ans[0]):
	print(b[only_s:])
elif ans[0] == -1:
	print('-')
else:
	print(b[:ans[1] + 1] + (b[ans[2]:] if ans[2] < len(b) else ''))


a = list(input())
b = list(input())
s = [-1]
i = 0
j = 0
while i < len(a) and j < len(b):
	if a[i] == b[j]:
		s.append(i)
		j += 1
	i += 1
e = [10 ** 6]
i = len(a) - 1
j = len(b) - 1
while i >= 0 and j >= 0:
	if a[i] == b[j]:
		e.append(i)
		j -= 1
	i -= 1
ans_len = 0
ans = ['-']
i = len(s) - 1
j = 0
while i >= 0 and j < len(e):
	if s[i] < e[j] and i + j - 1 < len(b):
		new_len = j + i
		if new_len > ans_len:
			ans_len = new_len
			if j > 0:
				ans = b[:i] + b[-j:]
			else:
				ans = b[:i]
		j += 1
	else:
		i -= 1
print(''.join(ans))


s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
dl = {}
dr = {}
i1 = 0
i2 = 0
while i1 < l1 and i2 < l2:
	while i1 < l1 and s1[i1] != s2[i2]:
		i1 += 1
	if i1 < l1:
		dl[i2] = i1
		i2 += 1
		i1 += 1
lmax = i2
if lmax == l2:
	print(s2)
else:
	i1 = l1 - 1
	i2 = l2 - 1
	while i1 >= 0 and i2 >= 0:
		while i1 >= 0 and s1[i1] != s2[i2]:
			i1 -= 1
		if i1 >= 0:
			dr[i2] = i1
			i2 -= 1
			i1 -= 1
	rmax = i2
	le = -1
	re = -1
	if l2 - lmax < rmax + 1:
		rcnt = l2 - lmax
		ls = 0
		rs = lmax
	else:
		rcnt = rmax + 1
		ls = rmax + 1
		rs = l2
	rr = rmax + 1
	for ll in range(lmax):
		while rr < l2 and (rr <= ll or dl[ll] >= dr[rr]):
			rr += 1
		if rr < l2:
			dif = rr - ll - 1
			if dif < rcnt:
				rcnt = dif
				ls = 0
				rs = ll + 1
				le = rr
				re = l2
	result = s2[ls:rs]
	if le != -1:
		result += s2[le:re]
	print(result if len(result) > 0 else '-')


import sys
(s, t) = (input(), '*' + input())
(n, m) = (len(s), len(t) - 1)
inf = 10 ** 9
(pre, suf) = ([-1] + [inf] * (m + 1), [-1] * (m + 1) + [n])
i = 0
for j in range(1, m + 1):
	while i < n and s[i] != t[j]:
		i += 1
	if i == n:
		break
	pre[j] = i
	i += 1
i = n - 1
for j in range(m, 0, -1):
	while 0 <= i and s[i] != t[j]:
		i -= 1
	if i == -1:
		break
	suf[j] = i
	i -= 1
(max_len, best_l, best_r) = (0, 0, 0)
j = 1
for i in range(m + 1):
	j = max(j, i + 1)
	while j <= m and pre[i] >= suf[j]:
		j += 1
	if pre[i] == inf:
		break
	if max_len < i + m + 1 - j:
		max_len = i + m + 1 - j
		(best_l, best_r) = (i, j)
pre_s = t[1:best_l + 1]
suf_s = t[best_r:]
print(pre_s + suf_s if max_len else '-')


a = input()
b = input()
x = []
j = 0
for i in range(len(a)):
	if j >= len(b):
		break
	if a[i] == b[j]:
		x.append(i)
		j += 1
y = []
j = len(b) - 1
for i in range(len(a) - 1, -1, -1):
	if j < 0:
		break
	if a[i] == b[j]:
		y.append(len(a) - i - 1)
		j -= 1
(lb, rb) = (0, 0)
ans = len(b)
if ans > len(b) - len(x):
	ans = len(b) - len(x)
	lb = len(x)
if ans > len(b) - len(y):
	ans = len(b) - len(y)
	lb = 0
	rb = len(y)
j = len(y) - 1
for i in range(len(x)):
	if i + j + 2 > len(b):
		j -= 1
	while j >= 0 and x[i] + y[j] + 2 > len(a):
		j -= 1
	if j < 0:
		break
	if ans > len(b) - i - j - 2:
		ans = len(b) - i - j - 2
		lb = i + 1
		rb = j + 1
if ans == len(b):
	print('-')
else:
	for i in range(lb):
		print(b[i], end='')
	for i in range(len(b) - rb, len(b)):
		print(b[i], end='')


from sys import stdin

def main():
	t = stdin.readline()
	s = stdin.readline()
	n = len(s) - 1
	m = len(t) - 1
	post = [-1] * n
	ss = n - 1
	st = m - 1
	while st >= 0 and ss >= 0:
		if t[st] == s[ss]:
			post[ss] = st
			ss -= 1
		st -= 1
	pre = [-1] * n
	ss = 0
	st = 0
	while st < m and ss < n:
		if t[st] == s[ss]:
			pre[ss] = st
			ss += 1
		st += 1
	low = 0
	high = n
	min_ans = n
	start = -1
	end = -1
	while low < high:
		mid = low + high >> 1
		ok = False
		if post[mid] != -1:
			if mid < min_ans:
				min_ans = mid
				start = 0
				end = mid - 1
				ok = True
		for i in range(1, n - mid):
			if pre[i - 1] != -1 and post[i + mid] != -1 and (post[i + mid] > pre[i - 1]):
				if mid < min_ans:
					min_ans = mid
					start = i
					end = i + mid - 1
					ok = True
		if pre[n - mid - 1] != -1:
			if mid < min_ans:
				min_ans = mid
				start = n - mid
				end = n - 1
				ok = True
		if not ok:
			low = mid + 1
		else:
			high = mid
	ans = []
	for i in range(n):
		if start <= i <= end:
			continue
		ans.append(s[i])
	if min_ans == n:
		print('-')
	else:
		print(''.join(ans))
main()