The only difference between easy and hard versions is the length of the string.

You are given a string $s$ and a string $t$, both consisting only of lowercase Latin letters. It is guaranteed that $t$ can be obtained from $s$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $s$ without changing order of remaining characters (in other words, it is guaranteed that $t$ is a subsequence of $s$).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from $s$ of maximum possible length such that after removing this substring $t$ will remain a subsequence of $s$.

If you want to remove the substring $s[l;r]$ then the string $s$ will be transformed to $s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$ (where $|s|$ is the length of $s$).

Your task is to find the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.


-----Input-----

The first line of the input contains one string $s$ consisting of at least $1$ and at most $2 \cdot 10^5$ lowercase Latin letters.

The second line of the input contains one string $t$ consisting of at least $1$ and at most $2 \cdot 10^5$ lowercase Latin letters.

It is guaranteed that $t$ is a subsequence of $s$.


-----Output-----

Print one integer — the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.


-----Examples-----
Input
bbaba
bb

Output
3

Input
baaba
ab

Output
2

Input
abcde
abcde

Output
0

Input
asdfasdf
fasd

Output
3

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms
Skill types: Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
s = input()
n = len(s)
t = input()
m = len(t)
rg = [0] * m
j = m - 1
for i in range(n):
	if s[n - 1 - i] == t[j]:
		rg[j] = n - 1 - i
		if j == 0:
			break
		j -= 1
lg = [0] * m
j = 0
for i in range(n):
	if s[i] == t[j]:
		lg[j] = i
		if j == m - 1:
			break
		j += 1
mx = max(rg[0], n - 1 - lg[-1])
for j in range(1, m):
	mx = max(mx, rg[j] - lg[j - 1] - 1)
print(mx)


s = input()
t = input()
r = [0] * len(t)
for i in range(len(t) - 1, -1, -1):
	p = len(s) - 1
	if i + 1 < len(t):
		p = r[i + 1] - 1
	while t[i] != s[p]:
		p -= 1
	r[i] = p
ans = p = 0
for i in range(len(s)):
	rp = len(s) - 1
	if p < len(t):
		rp = r[p] - 1
	ans = max(rp - i + 1, ans)
	if p < len(t) and t[p] == s[i]:
		p += 1
print(ans)


str1 = input()
str2 = input()
(n, m) = (len(str1), len(str2))
(pos, i) = ([], 0)
for p in range(n):
	if i == m:
		break
	if str1[p] == str2[i]:
		pos.append(p)
		i += 1
pos = [-1] + pos + [n]
ans = 0
for i in range(1, m + 2):
	ans = max(ans, pos[i] - pos[i - 1] - 1)
i = 0
for p in range(n - 1, -1, -1):
	if i == m:
		break
	if str1[p] == str2[m - i - 1]:
		ans = max(ans, p - pos[m - i - 1] - 1)
		i += 1
print(ans)


from sys import stdin
input = stdin.readline
s = input()
t = input()
n = len(t)
low = [0 for i in range(len(t))]
high = [0 for i in range(len(t))]
acc = 0
for i in range(n):
	acc_t = t[i]
	while acc_t != s[acc]:
		acc += 1
	low[i] = acc
	acc += 1
acc = len(s) - 1
for i in range(len(t)):
	acc_t = t[n - i - 1]
	while acc_t != s[acc]:
		acc -= 1
	high[n - i - 1] = acc
	acc -= 1
res = max(high[0], len(s) - low[n - 1] - 1)
for i in range(n - 1):
	res = max(res, high[i + 1] - low[i] - 1)
print(res)


big = input()
small = input()
left = [0] * (len(small) + 1)
left[0] = -1
wsk = -1
for i in range(1, len(small) + 1):
	while True:
		wsk += 1
		if big[wsk] == small[i - 1]:
			left[i] = wsk
			break
big = big[::-1]
small = small[::-1]
right = [0] * (len(small) + 1)
right[0] = -1
wsk = -1
for i in range(1, len(small) + 1):
	while True:
		wsk += 1
		if big[wsk] == small[i - 1]:
			right[i] = wsk
			break
wyn = 100000000
for i in range(len(left)):
	wyn = min(wyn, right[i] + left[len(left) - 1 - i] + 2)
print(len(big) - wyn)


s = input()
t = input()
(f, b) = ([], [])
cur = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == t[cur]:
		b.append(i)
		cur -= 1
	if cur == -1:
		break
b.sort()
cur = 0
for i in range(len(s)):
	if s[i] == t[cur]:
		f.append(i)
		cur += 1
	if cur == len(t):
		break
ans = max(b[0], len(s) - f[-1] - 1)
bbb = 0
bbb ^= 1
bbb += 1
for i in range(len(f) - 1):
	ans = max(ans, abs(b[i + 1] - 1 - f[i]))
print(ans)


from sys import stdin, stdout
input = stdin.readline
(s, t) = list(map(str, stdin.read().split()))
(n, m) = (len(s), len(t))
a = [0] * m
b = [0] * m
pos = 0
for i in range(n):
	if s[i] == t[pos]:
		a[pos] = i
		pos += 1
		if pos == m:
			break
pos = m - 1
for i in range(n - 1, -1, -1):
	if s[i] == t[pos]:
		b[pos] = i
		pos -= 1
		if pos == -1:
			break
res = max(b[0], n - (a[-1] + 1))
for i in range(m - 1):
	res = max(res, b[i + 1] - 1 - (a[i] + 1) + 1)
print(res)


from sys import stdin
s = stdin.readline().strip()
s1 = stdin.readline().strip()
dp = [-1 for i in range(len(s1) + 1)]
dp1 = [-1 for i in range(len(s1) + 1)]
x = 0
for i in range(len(s)):
	if s[i] == s1[x]:
		dp[x + 1] = i
		x += 1
		if x >= len(s1):
			break
x = len(s1) - 1
y = 1
dp[0] = -1
dp1[0] = len(s)
for i in range(len(s) - 1, -1, -1):
	if s[i] == s1[x]:
		dp1[y] = i
		x -= 1
		y += 1
		if x < 0:
			break
ans = 0
for i in range(len(s1) + 1):
	ans = max(dp1[len(s1) - i] - dp[i] - 1, ans)
	ans = max(dp[len(s1) - i] - dp1[i] - 1, ans)
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bs(a, l, h, x):
	while l < h:
		mid = (l + h) // 2
		if a[mid] == x:
			return mid
		if a[mid] < x:
			l = mid + 1
		else:
			h = mid
	return l

def sieve(a):
	for i in range(3, 10 ** 6 + 1, 2):
		a[i] = 1
	for i in range(3, 10 ** 6 + 1, 2):
		for j in range(i * i, 10 ** 6 + 1, i):
			a[j] = 0
	a[2] = 1
	return a

def solve():
	s = list(inp())
	t = list(inp())
	left = [0] * len(s)
	j = 0
	for i in range(0, len(s)):
		if j >= len(t):
			left[i] = left[i - 1]
			continue
		if s[i] == t[j]:
			j += 1
			if i == 0:
				left[i] = 1
				continue
			left[i] = left[i - 1] + 1
		else:
			if i == 0:
				continue
			left[i] = left[i - 1]
	right = [0] * len(s)
	j = len(t) - 1
	for i in range(len(s) - 1, -1, -1):
		if j < 0:
			right[i] = right[i + 1]
			continue
		if t[j] == s[i]:
			j -= 1
			if i == len(s) - 1:
				right[i] = 1
				continue
			right[i] = right[i + 1] + 1
		else:
			if i == len(s) - 1:
				continue
			right[i] = right[i + 1]
	ans = 0
	for i in range(0, len(s)):
		if left[i] == len(t):
			ans = max(ans, len(s) - (i + 1))
			break
	for i in range(len(s) - 1, -1, -1):
		if right[i] == len(t):
			ans = max(ans, i)
			break
	right = right[::-1]
	for i in range(0, len(s) - 1):
		ind = bl(right, len(t) - left[i])
		ind = len(right) - ind - 1
		if ind >= i + 2:
			ans = max(ans, ind - i - 1)
	print(ans)
testcase(1)


import sys
s = sys.stdin.readline()
t = sys.stdin.readline()
(sn, tn) = (len(s), len(t))
(left, right) = ([0] * tn, [0] * tn)
(prev, last) = (-1, sn)
for i in range(tn):
	left[i] = prev = s.find(t[i], prev + 1)
	right[tn - i - 1] = last = s.rfind(t[tn - i - 1], 0, last)
ans = max((right[i + 1] - left[i] - 1 for i in range(tn - 1)))
print(max(right[0], sn - left[-1] - 1, ans))


import sys, math, queue
MOD = 998244353
sys.setrecursionlimit(1000000)
(t, s) = (input(), input())
dp1 = [-1 for i in range(len(s))]
dp2 = [-1 for i in range(len(s))]
j = 0
for i in range(len(s)):
	while t[j] != s[i]:
		j += 1
	dp1[i] = j
	j += 1
j = len(t) - 1
for i in reversed(range(len(s))):
	while t[j] != s[i]:
		j -= 1
	dp2[i] = j
	j -= 1
ans = max(dp1[0], len(t) - dp1[-1] - 1, dp2[0], len(t) - dp2[-1] - 1)
for i in range(1, len(s)):
	ans = max(ans, dp2[i] - dp1[i - 1] - 1)
print(ans)


import sys
from collections import defaultdict
import math

def main():
	s = input()
	t = input()
	longest_prefix = [0] * len(s)
	longest_suffix = [0] * len(s)
	longest_prefix[0] = 1 if s[0] == t[0] else 0
	for i in range(1, len(s)):
		x = longest_prefix[i - 1]
		if x == len(t) or s[i] != t[x]:
			longest_prefix[i] = x
		else:
			longest_prefix[i] = x + 1
	longest_suffix[-1] = 1 if s[-1] == t[-1] else 0
	for i in range(len(s) - 2, -1, -1):
		x = longest_suffix[i + 1]
		if x == len(t) or s[i] != t[-1 - x]:
			longest_suffix[i] = x
		else:
			longest_suffix[i] = x + 1
	res = 0
	pos1 = 0
	while longest_prefix[pos1] != len(t):
		pos1 += 1
	res = max(res, len(s) - 1 - pos1)
	pos2 = len(s) - 1
	while longest_suffix[pos2] != len(t):
		pos2 -= 1
	res = max(res, pos2)
	pos1 = 0
	pos2 = 0
	while pos1 < len(s):
		while pos2 + 1 < len(s) and longest_prefix[pos1] + longest_suffix[pos2 + 1] >= len(t):
			pos2 += 1
		res = max(res, pos2 - pos1 - 1)
		pos1 += 1
	print(res)

def __starting_point():
	main()
__starting_point()


s = input()
t = input()
n = len(t)
b = [0] * (len(s) + 1)
a = [0] * (len(s) + 1)
c = 0
for i in range(len(s)):
	if c == n:
		b[i + 1] = c
	elif s[i] == t[c]:
		c += 1
		b[i + 1] = c
	else:
		b[i + 1] = c
c = n - 1
for i in range(len(s) - 1, -1, -1):
	if c == -1:
		a[i] = n
	elif s[i] == t[c]:
		c -= 1
		a[i] = n - c - 1
	else:
		a[i] = n - c - 1
st = 1
e = 1
m = 0
a = [0] + a
b.append(0)
while e < len(s):
	if b[st - 1] + a[e + 1] >= len(t):
		m = max(m, e - st + 1)
		e += 1
	else:
		st += 1
	if st > e:
		e += 1
if b[st - 1] + a[e + 1] >= len(t):
	m = max(m, e - st + 1)
else:
	while st <= len(s):
		if b[st - 1] + a[e + 1] >= len(t):
			m = max(m, e - st + 1)
			break
		st += 1
print(m)


from sys import stdin, stdout
s = stdin.readline().strip()
t = stdin.readline().strip()
leftmost = [-1]
ptr1 = ptr2 = 0
while ptr2 < len(t):
	if s[ptr1] == t[ptr2]:
		leftmost.append(ptr1)
		ptr1 += 1
		ptr2 += 1
	else:
		ptr1 += 1
rightmost = []
ptr1 = len(s) - 1
ptr2 = len(t) - 1
while ptr2 >= 0:
	if s[ptr1] == t[ptr2]:
		rightmost.append(ptr1)
		ptr1 -= 1
		ptr2 -= 1
	else:
		ptr1 -= 1
rightmost.reverse()
rightmost.append(len(s))
ans = -1
for i in range(len(leftmost)):
	ans = max(ans, rightmost[i] - leftmost[i] - 1)
stdout.write(str(ans) + '\n')


s = input()
t = input()
(n, m) = (len(s), len(t))
ans = 0
max_pos = [-1 for i in range(m)]
max_pos.append(n)
j = m - 1
for i in range(n - 1, -1, -1):
	if j < 0:
		ans = max(ans, i + 1)
		break
	if j >= 0 and s[i] == t[j]:
		max_pos[j] = i
		j -= 1
curr = 0
for i in range(n):
	if curr < m and t[curr] == s[i]:
		ans = max(ans, max_pos[curr + 1] - i - 1)
		curr += 1
print(ans)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
s = input()
t = input()
n = len(s)
m = len(t)
ind = defaultdict(lambda : [-1, -1])
i = 0
j = 0
while j < m:
	if s[i] == t[j]:
		ind[j][0] = i
		j += 1
	i += 1
i = n - 1
j = m - 1
while j >= 0:
	if s[i] == t[j]:
		ind[j][1] = i
		j -= 1
	i -= 1
ans = max(ind[0][1], n - ind[m - 1][0] - 1)
for i in range(1, m):
	ans = max(ans, ind[i][1] - ind[i - 1][0] - 1)
print(ans)


s = str(input())
t = str(input())
a = []
i = 0
j = 0
while j < len(t):
	if s[i] == t[j]:
		a.append(i + 1)
		j += 1
	i += 1
b = [0] * len(t)
i = len(s) - 1
j = len(t) - 1
while j >= 0:
	if s[i] == t[j]:
		b[j] = i + 1
		j -= 1
	i -= 1
maxi = max(b[0] - 1, len(s) - a[-1])
for i in range(len(t) - 1):
	maxi = max(maxi, b[i + 1] - a[i] - 1)
print(maxi)


s = list(input())
t = list(input())
fo = []
ti = 0
for (i, c) in enumerate(s):
	if c == t[ti]:
		ti += 1
		fo.append(i)
		if ti == len(t):
			break
lo = []
ti = len(t) - 1
for i in reversed(range(len(s))):
	c = s[i]
	if c == t[ti]:
		ti -= 1
		lo.append(i)
		if ti == -1:
			break
mx = max(len(s) - fo[-1] - 1, lo[-1])
lo.reverse()
for i in range(1, len(t)):
	mx = max(mx, lo[i] - fo[i - 1] - 1)
print(mx)


s = input()
t = input()
s2 = s[::-1]
t2 = t[::-1]
n = len(s)
m = len(t)
pos = [0] * m
j = 0
for i in range(n):
	if s[i] == t[j]:
		pos[j] = i
		j += 1
		if j == m:
			break
pos2 = [0] * m
j = 0
for i in range(n):
	if s2[i] == t2[j]:
		pos2[j] = i
		j += 1
		if j == m:
			break
ans = max(pos[0], pos2[0], n - pos[-1] - 1, n - pos2[-1] - 1)
e = -(m - 1)
for j in range(m - 1):
	ans = max(ans, abs(n - pos2[-(j + 2)] - 1 - pos[j]) - 1)
print(ans)


s = input()
t = input()
i = 0
l = []
for c in t:
	while s[i] != c:
		i += 1
	l.append(i)
	i += 1
i = len(s) - 1
r = []
for c in t[::-1]:
	while s[i] != c:
		i -= 1
	r.append(i)
	i -= 1
r.reverse()
mx = r[0]
for i in range(len(t) - 1):
	mx = max(mx, r[i + 1] - l[i] - 1)
mx = max(mx, len(s) - l[-1] - 1)
print(mx)


from collections import deque
import sys, math, bisect

def inp():
	return sys.stdin.readline().strip()
s = inp()
t = inp()
n = len(s)
m = len(t)
mps = [0] * n
mss = [0] * n
idx = 0
for i in range(n):
	if idx < m and t[idx] == s[i]:
		mps[i] = idx + 1
		idx += 1
	else:
		mps[i] = idx
idx = m
for i in range(n - 1, -1, -1):
	if idx >= 1 and t[idx - 1] == s[i]:
		mss[i] = idx
		idx -= 1
	else:
		mss[i] = idx
mxl = 0
prev = 0
for l in range(n):
	r = bisect.bisect_right(mss, prev) - 1
	mxl = max(mxl, r - l + 1)
	prev = mps[l]
print(mxl)


s = input()
t = input()
(n, m) = (len(s), len(t))
(l, r, j) = ([0] * m, [0] * m, 0)
for i in range(m):
	while s[j] != t[i]:
		j += 1
	l[i] = j
	j += 1
j = n - 1
for i in range(m - 1, -1, -1):
	while s[j] != t[i]:
		j -= 1
	r[i] = j
	j -= 1
ans = max(0, r[0], n - 1 - l[-1])
for i in range(m - 1):
	ans = max(ans, r[i + 1] - l[i] - 1)
print(ans)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
s = input()
t = input()
a = [0]
b = [0]
j = 0
for i in t:
	for k in range(j, len(s)):
		if i == s[k]:
			a.append(k)
			j = k + 1
			break
a.append(len(s))
s = s[::-1]
t = t[::-1]
j = 0
for i in t:
	for k in range(j, len(s)):
		if i == s[k]:
			b.append(k)
			j = k + 1
			break
ans = 0
b.append(len(s))
for i in range(1, len(a)):
	ans = max(ans, a[i] - a[i - 1] - 1, b[i] - b[i - 1] - 1)
b = [len(s)] + [len(s) - i - 1 for i in b[1:-1]] + [0]
b = list(reversed(b))
for i in range(1, len(a)):
	ans = max(ans, a[i] - b[i - 1] - 1, b[i] - a[i - 1] - 1)
print(ans)


s = input()
t = input()
s_pos = [len(s) for i in range(len(t))]
(i, j) = (len(s) - 1, len(t) - 1)
while i > -1 and j > -1:
	if s[i] == t[j]:
		s_pos[j] = i
		j -= 1
	i -= 1
(p, q) = (0, 0)
ans = 0
while p < len(s):
	if q == len(t):
		ans = max(ans, len(s) - p)
		break
	remove = s_pos[q] - p
	ans = max(ans, remove)
	if s[p] == t[q]:
		q += 1
	p += 1
print(ans)


s = input()
t = input()
n = len(t)
first = [0] * n
last = [0] * n
p = 0
i = 0
while p < n:
	if s[i] == t[p]:
		first[p] = i
		p += 1
	i += 1
p = n - 1
i = len(s) - 1
while p >= 0:
	if s[i] == t[p]:
		last[p] = i
		p -= 1
	i -= 1
ans = max(last[0], len(s) - 1 - first[-1])
for i in range(n - 1):
	ans = max(ans, last[i + 1] - first[i] - 1)
print(ans)


from collections import deque

def substr_idx(s, t, reverse=False):
	idx = deque()
	i = 0
	rng = range(len(s))
	if reverse:
		rng = reversed(rng)
	for k in rng:
		if i >= len(t):
			break
		if reverse and s[k] == t[-i - 1]:
			idx.appendleft(k)
			i += 1
		elif not reverse and s[k] == t[i]:
			idx.append(k)
			i += 1
	return idx
s = input()
t = input()
idleft = substr_idx(s, t)
idright = substr_idx(s, t, reverse=True)
m = max(idright[0], len(s) - idleft[-1] - 1)
for i in range(1, len(idleft)):
	m = max(m, idright[i] - idleft[i - 1] - 1)
print(m)


s = input()
t = input()

def compute_prefix(s, t):
	prefix = [0 for i in range(len(t) + 1)]
	i = 0
	j = 0
	while i < len(t):
		while s[j] != t[i]:
			j += 1
		prefix[i + 1] = j + 1
		i += 1
		j += 1
	return prefix
prefix = compute_prefix(s, t)
suffix = compute_prefix(s[::-1], t[::-1])
res = 0
for i in range(len(t) + 1):
	res = max(res, len(s) - (prefix[i] + suffix[len(t) - i]))
print(res)


word = input()
sub = input()
n = len(word)
m = len(sub)
LR = []
RL = []
ind = 0
for i in range(n):
	if sub[ind] == word[i]:
		LR.append(i)
		ind += 1
		if ind == m:
			break
ind = m - 1
for i in range(n - 1, -1, -1):
	if sub[ind] == word[i]:
		RL.append(i)
		ind -= 1
		if ind == -1:
			break
RL.reverse()
mn = max(n - LR[-1] - 1, RL[0])
for i in range(m - 1):
	d = RL[i + 1] - LR[i] - 1
	if d > mn:
		mn = d
print(mn)


s = input()
t = input()
l = 0
pre = []
suf = []
for i in range(len(s)):
	if s[i] == t[l]:
		pre.append(i)
		l += 1
	if l == len(t):
		break
l = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == t[l]:
		suf.append(i)
		l -= 1
	if l == -1:
		break
pre.sort()
suf.sort()
ans = 0
ans = max(suf[0], len(s) - pre[-1] - 1)
for i in range(len(t) - 1):
	ans = max(ans, abs(suf[i + 1] - pre[i] - 1))
print(ans)


def process(s, t):
	l = []
	r = [0] * len(t)
	j = 0
	for i in range(len(t)):
		while s[j] != t[i]:
			j += 1
		l.append(j)
		j += 1
	j = len(s) - 1
	for i in reversed(range(len(t))):
		while s[j] != t[i]:
			j -= 1
		r[i] = j
		j -= 1
	res = max(r[0], len(s) - 1 - l[-1])
	for i in range(len(t) - 1):
		res = max(res, r[i + 1] - l[i] - 1)
	return res
s = input()
t = input()
print(process(s, t))


import sys
inf = float('inf')
(mod, MOD) = (1000000007, 998244353)

def is_subsq(a, b):
	i = 0
	j = 0
	while i < len(b) and j < len(a):
		if a[j] == b[i]:
			j += 1
		i += 1
	return j == len(a)

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
s = input()
t = input()
n = len(s)
m = len(t)
l = [-1]
r = [n]
c = 0
for i in range(n):
	if s[i] == t[c]:
		l.append(i)
		c += 1
		if c >= m:
			break
c = 0
for i in range(n):
	if s[-1 - i] == t[-1 - c]:
		r.append(n - 1 - i)
		c += 1
		if c >= m:
			break
mx = 0
for i in range(m + 1):
	mx = max(mx, r[m - i] - l[i] - 1)
print(mx)


(z, zz) = (input, lambda : list(map(int, z().split())))
zzz = lambda : [int(i) for i in stdin.readline().split()]
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from string import *
from re import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from itertools import accumulate as ac

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2 or x == 0:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
s = z()
t = z()
ans = 0
lst = [0] * len(t)
for i in range(len(t) - 1, -1, -1):
	pos = len(s) - 1
	if i + 1 < len(t):
		pos = lst[i + 1] - 1
	while s[pos] != t[i]:
		pos -= 1
	lst[i] = pos
ans = 0
pos = 0
for i in range(len(s)):
	rpos = len(s) - 1
	if pos < len(t):
		rpos = lst[pos] - 1
	ans = max(ans, rpos - i + 1)
	if pos < len(t) and t[pos] == s[i]:
		pos += 1
print(ans)
exit()
for i in range(len(s)):
	for j in range(i, len(s)):
		pos = 0
		for p in range(len(s)):
			if i <= p and p <= j:
				continue
			if pos < len(t) and t[pos] == s[p]:
				pos += 1
		if pos == len(t):
			ans = max(ans, j - i + 1)
print(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq

def main():
	s = input()
	t = input()
	(n, m) = (len(s), len(t))
	(i, j) = (0, 0)
	first = []
	last = []
	while j < m:
		if s[i] == t[j]:
			first.append(i)
			i += 1
			j += 1
		else:
			i += 1
	(i, j) = (n - 1, m - 1)
	while j >= 0:
		if s[i] == t[j]:
			last.append(i)
			j -= 1
		i -= 1
	last = last[::-1]
	ans = max(last[0], n - first[-1] - 1)
	for i in range(m - 1):
		ans = max(ans, last[i + 1] - first[i] - 1)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


s = ' ' + input() + ' '
t = ' ' + input() + ' '
f = [0]
cnt = 0
for i in range(1, len(s)):
	f.append(f[i - 1])
	if s[i] == t[cnt + 1]:
		cnt += 1
		f[i] += 1
s = s[::-1]
t = t[::-1]
g = [0]
cnt = 0
for i in range(1, len(s)):
	g.append(g[i - 1])
	if s[i] == t[cnt + 1]:
		cnt += 1
		g[i] += 1
g = g[::-1]
ans = l = r = 0
while l < len(s):
	while r < len(s) and f[l] + g[r] >= len(t) - 2:
		r += 1
	ans = max(ans, r - l - 2)
	l += 1
print(ans)


def int_multiple():
	return [int(c) for c in input().split()]

def int_single():
	return int(input())

def str_multiple():
	return [c for c in input().split()]

def str_single():
	return input()
s = str_single()
t = str_single()
ti = 0
start = []
for si in range(len(s)):
	if s[si] == t[ti]:
		start.append(si)
		ti += 1
		if ti == len(t):
			break
end = []
ti = len(t) - 1
for si in reversed(list(range(len(s)))):
	if s[si] == t[ti]:
		end.append(si)
		ti -= 1
		if ti < 0:
			break
end = list(reversed(end))
start_mx = len(s) - start[-1] - 1
end_mx = end[0]
mx_between = 0
for i in range(len(t) - 1):
	diff = end[i + 1] - start[i] - 1
	mx_between = max(mx_between, diff)
print(max(start_mx, end_mx, mx_between))


def find_first(s, t):
	idx = 0
	l = [-1]
	for i in range(len(s)):
		if t[idx] == s[i]:
			l.append(i)
			idx += 1
		if idx == len(t):
			return l
	return None

def find_last(s, t):
	idx = len(t) - 1
	l = [len(s)]
	for i in range(len(s) - 1, -1, -1):
		if t[idx] == s[i]:
			l.append(i)
			idx -= 1
		if idx == -1:
			return l[::-1]
	return None
bigstr = input()
substr = input()
first = find_first(bigstr, substr)
last = find_last(bigstr, substr)
mx = 0
for idx in range(len(first)):
	mx = max(mx, last[idx] - first[idx] - 1)
print(mx)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
from decimal import *

def solve():
	s = inp()
	t = inp()
	n = len(s)
	l = len(t)
	ar1 = []
	ar2 = []
	j = 0
	for i in range(n):
		if s[i] == t[j]:
			ar1.append(i)
			j += 1
			if j >= l:
				break
	j = l - 1
	for i in range(n - 1, -1, -1):
		if s[i] == t[j]:
			ar2.append(i)
			j -= 1
			if j < 0:
				break
	ar2 = ar2[::-1]
	m = max(n - 1 - ar1[l - 1], ar2[0])
	for i in range(l - 1):
		m = max(m, ar2[i + 1] - ar1[i] - 1)
	print(m)
solve()


def naiveSolve(n):
	return

def main():
	s = '$' + input() + '$'
	t = '$' + input() + '$'
	n = len(t)
	left = [-1] * n
	right = [-1] * n
	m = len(s)
	j = 0
	for i in range(m):
		if s[i] == t[j]:
			left[j] = i
			j += 1
			if j == n:
				break
	j = n - 1
	for i in range(m - 1, -1, -1):
		if s[i] == t[j]:
			right[j] = i
			j -= 1
			if j == -1:
				break
	ans = 0
	for i in range(n - 1):
		ans = max(ans, right[i + 1] - left[i] - 1)
	print(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as bsl
from collections import defaultdict
S = [k for k in input()]
T = [k for k in input()]
need = set(T)
n = len(S)
dict1 = defaultdict(list)
for s in range(n):
	if S[s] in need:
		dict1[S[s]].append(s)
tt = dict1[T[-1]][-1]
dict2 = {(T[-1], len(T) - 1): tt}
for s in range(len(T) - 2, -1, -1):
	orig = min(bsl(dict1[T[s]], tt), len(dict1[T[s]]) - 1)
	if dict1[T[s]][orig] >= tt:
		orig -= 1
	tt = dict1[T[s]][orig]
	dict2[T[s], s] = tt
maxsofar = tt
indsofar = dict1[T[0]][0]
for s in range(1, len(T)):
	maxsofar = max(maxsofar, dict2[T[s], s] - 1 - indsofar)
	ind = min(bsl(dict1[T[s]], indsofar), len(dict1[T[s]]) - 1)
	if T[s] == T[s - 1]:
		ind += 1
	indsofar = dict1[T[s]][ind]
maxsofar = max(maxsofar, n - 1 - indsofar)
print(maxsofar)


s = input()
t = input()
pos = [[-1, -1] for i in range(len(t))]
ptr = 0
for (i, c) in enumerate(t):
	while s[ptr] != c:
		ptr += 1
	pos[i][0] = ptr
	ptr += 1
ptr = len(s) - 1
for i in range(len(t) - 1, -1, -1):
	c = t[i]
	while s[ptr] != c:
		ptr -= 1
	pos[i][1] = ptr
	ptr -= 1
best = max(pos[0][1], len(s) - pos[-1][0] - 1)
for i in range(1, len(pos)):
	best = max(best, pos[i][1] - pos[i - 1][0] - 1)
print(best)


import sys
import math
input = sys.stdin.readline
s1 = input()
t1 = input()
s = s1.rstrip()
t = t1.rstrip()
mini = list()
maxi = list()
st = 0
for i in range(len(s)):
	if s[i] == t[st]:
		mini.append(i)
		st += 1
	if st == len(t):
		break
st = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == t[st]:
		maxi.append(i)
		st -= 1
	if st == -1:
		break
maxi.reverse()
ans = maxi[0]
ans = max(len(s) - 1 - mini[len(t) - 1], ans)
for i in range(1, len(t)):
	ans = max(maxi[i] - mini[i - 1] - 1, ans)
if len(s) == len(t):
	print(0)
else:
	print(ans)


a = input().strip()
b = input().strip()
(n, m) = (len(a), len(b))
p = m - 1
en = [-1] * m
for j in range(n - 1, -1, -1):
	if a[j] == b[p]:
		en[p] = j
		p -= 1
	if p == -1:
		break
st = [-1] * m
p = 0
for j in range(n):
	if a[j] == b[p]:
		st[p] = j
		p += 1
	if p == m:
		break
an = max(en[0], n - 1 - st[-1])
for i in range(m - 1):
	an = max(an, en[i + 1] - st[i] - 1)
print(an)


s = input()
t = input()
pr = []
pospr = []
j = 0
for i in range(len(s)):
	if j != len(t) and s[i] == t[j]:
		j += 1
		pospr.append(i)
	pr.append(j)
suf = [0] * len(s)
j = len(t) - 1
possuf = [0] * len(t)
for i in range(len(s) - 1, -1, -1):
	if j != -1 and s[i] == t[j]:
		possuf[j] = i
		j -= 1
	suf[i] = len(t) - j - 1
ans = 0
for i in range(len(s)):
	sym = pr[i - 1] if i != 0 else 0
	last = possuf[sym] if sym != len(t) else len(s)
	if last - i > ans:
		ans = last - i
print(ans)


import sys

def input():
	return sys.stdin.readline().rstrip()

def slv():
	S = input()
	T = input()
	n = len(T)
	needcntl = [0] * (n + 1)
	needcntr = [0] * (n + 1)
	idx = 0
	i = 0
	while i < n:
		if T[i] == S[idx]:
			needcntl[i + 1] = idx + 1
			i += 1
		idx += 1
	S = S[::-1]
	T = T[::-1]
	idx = 0
	i = 0
	while i < n:
		if T[i] == S[idx]:
			needcntr[i + 1] = idx + 1
			i += 1
		idx += 1
	ans = 0
	for j in range(n + 1):
		remove_cnt = needcntl[j] + needcntr[n - j]
		ans = max(ans, len(S) - remove_cnt)
	print(ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


import sys
from collections import defaultdict as dd
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
st = input()
pat = input()
n = len(st)
forward = [0 for i in range(n)]
idx = 0
for i in range(n):
	if idx < len(pat) and st[i] == pat[idx]:
		idx += 1
		forward[i] = idx
backward = [0 for x in range(n)]
idx = len(pat) - 1
for i in range(n - 1, -1, -1):
	if idx >= 0 and st[i] == pat[idx]:
		idx -= 1
		backward[i] = idx + 2
c1 = dd(int)
c2 = dd(int)
for i in range(n):
	c1[forward[i]] = i + 1
	c2[backward[i]] = i + 1
ans = max(c2[1] - 1, n - c1[len(pat)])
for i in range(1, len(pat)):
	ans = max(ans, abs(c1[i] - c2[i + 1]) - 1)
print(ans)


big = input()
small = input()
pre = []
post = []
i = 0
j = 0
while 1:
	if j == len(small):
		break
	if big[i] == small[j]:
		pre.append(i)
		i += 1
		j += 1
	else:
		i += 1
big = big[::-1]
small = small[::-1]
i = 0
j = 0
while 1:
	if j == len(small):
		break
	if big[i] == small[j]:
		post.append(i)
		i += 1
		j += 1
	else:
		i += 1
for i in range(len(small)):
	post[i] = len(big) - 1 - post[i]
post.reverse()
ans = max(post[0], len(big) - (pre[-1] + 1))
for i in range(len(small) - 1):
	ans = max(ans, post[i + 1] - (pre[i] + 1))
print(ans)


s = input()
t = input()
indl = [-1 for i in range(len(t))]
j = 0
for i in range(len(s)):
	if s[i] == t[j]:
		indl[j] = i
		j += 1
		if j == len(t):
			break
indr = [-1 for i in range(len(t))]
j = len(t) - 1
for i1 in range(len(s)):
	i = len(s) - 1 - i1
	if s[i] == t[j]:
		indr[j] = i
		j -= 1
		if j == -1:
			break
l = indr[0]
for i in range(len(t) - 1):
	l = max(l, indr[i + 1] - indl[i] - 1)
l = max(l, len(s) - 1 - indl[len(t) - 1])
print(l)


R = lambda : map(int, input().split())
s = input()
t = input()
(ls, lt) = (len(s), len(t))
a = [0] * lt
j = ls - 1
for i in reversed(range(lt)):
	while s[j] != t[i]:
		j -= 1
	a[i] = j
	j -= 1
(res, l) = (0, 0)
for i in range(ls):
	rp = ls - 1
	if l < lt:
		rp = a[l] - 1
	res = max(res, rp - i + 1)
	if l < lt and s[i] == t[l]:
		l += 1
print(res)


from math import *

def nextInt():
	return int(input())

def nextInts():
	return list(map(int, input().split()))

def need(s, t):
	cur = 0
	res = [cur]
	for c in t:
		while s[cur] != c:
			cur += 1
		cur += 1
		res.append(cur)
	return res

def solve():
	s = input()
	t = input()
	x = need(s, t)
	s = ''.join(reversed(s))
	t = t[::-1]
	y = need(s, t)
	ans = 1000000000.0
	for i in range(len(x)):
		ans = min(ans, x[i] + y[len(x) - 1 - i])
	return len(s) - ans
print(solve())


S = input()
T = input()
(N, M) = (len(S), len(T))

def calc(s, t):
	X = [0] * len(s)
	j = 0
	for i in range(len(s)):
		if j >= len(t):
			X[i] = j
		elif s[i] == t[j]:
			X[i] = j + 1
			j += 1
		else:
			X[i] = X[i - 1]
	return [0] + X
(A, B) = (calc(S, T), calc(S[::-1], T[::-1])[::-1])
(l, r) = (0, N)
while r - l > 1:
	m = (l + r) // 2
	C = [A[i] + B[i + m] for i in range(N - m + 1)]
	if max(C) >= M:
		l = m
	else:
		r = m
print(l)


s = input()
t = input()

def search(s, t):
	indext = 0
	pos = [-1]
	for i in range(len(s)):
		if indext < len(t) and s[i] == t[indext]:
			pos += [i]
			indext += 1
		if indext == len(t):
			return pos
pos = search(s, t)
right = len(s) - 1
ans = right - pos[-1]
for i in range(len(t))[::-1]:
	while s[right] != t[i]:
		right -= 1
	right -= 1
	ans = max(ans, right - pos[i])
print(ans)


import sys
input = sys.stdin.readline
from math import gcd, sqrt
s = input().strip()
t = input().strip()
l = []
n = len(s)
m = len(t)
p = n - 1
q = m - 1
while q >= 0:
	if s[p] == t[q]:
		l.append(p)
		p -= 1
		q -= 1
	else:
		p -= 1
l.reverse()
l.append(n)
ans = l[0]
p = 0
q = 0
r = 0
while r < m:
	if s[p] == t[q]:
		ans = max(ans, l[r + 1] - p - 1)
		q += 1
		r += 1
		p += 1
	else:
		p += 1
print(ans)


a = list(input())
b = list(input())
l = [0 for i in range(len(a))]
r = [0 for i in range(len(a))]
itr = 0
m = len(b)
n = len(a)
for i in range(len(a)):
	if itr < m and b[itr] == a[i]:
		itr += 1
	l[i] = itr
itr = 0
for i in range(len(a)):
	if itr < m and b[m - 1 - itr] == a[n - 1 - i]:
		itr += 1
	r[n - 1 - i] = itr
ans = 0
for i in range(n):
	left = 1
	right = n - i
	mid = 0
	while left <= right:
		mid = (left + right) // 2
		if l[i] + r[i + mid - 1] >= m:
			ans = max(ans, mid - 2)
			left = mid + 1
		else:
			right = mid - 1
for i in range(n):
	if l[i] == 1:
		ans = max(ans, i)
		break
for i in range(n):
	if l[n - 1 - i] == m:
		ans = max(ans, i)
for i in range(n):
	if r[i] == m:
		ans = max(ans, i)
for i in range(n):
	if r[n - 1 - i] == 1:
		ans = max(ans, i)
		break
print(ans)


def main():
	string = input()
	substring = input()
	size = len(substring)
	string_size = len(string)
	first = []
	last = []
	first.append(-1)
	index = 0
	for i in range(string_size):
		c = string[i]
		if c == substring[index]:
			first.append(i)
			index = index + 1
		if index >= size:
			break
	last.append(len(string))
	index = size - 1
	for i in range(string_size):
		c = string[string_size - i - 1]
		if c == substring[index]:
			last.append(string_size - i - 1)
			index = index - 1
		if index < 0:
			break
	last = last[::-1]
	m = 0
	for i in range(size + 1):
		length = last[i] - first[i]
		if length > m:
			m = length
	print(m - 1)
main()


s = input()
t = input()
(l, r) = ([0] * len(t), [0] * len(t))
(li, ri) = (0, len(s) - 1)
for i in range(len(t)):
	while s[li] != t[i]:
		li = li + 1
	while s[ri] != t[-i - 1]:
		ri = ri - 1
	l[i] = li
	r[-i - 1] = ri
	li += 1
	ri -= 1
print(max([r[0], len(s) - l[-1] - 1] + [max(0, r[i] - l[i - 1]) - 1 for i in range(1, len(t))]))


s = input()
t = input()
dfirst = {}
dlast = {}
mx = -99
x = 0
for i in range(len(t)):
	while s[x] != t[i]:
		x += 1
	dfirst[i] = x
	if i == len(t) - 1:
		mx = max(mx, len(s) - x - 1)
	x += 1
x = len(s) - 1
trev = t[::-1]
for i in range(len(trev)):
	while s[x] != trev[i]:
		x -= 1
	dlast[len(t) - 1 - i] = x
	if i == len(trev) - 1:
		mx = max(mx, x)
	x -= 1
for i in range(1, len(t)):
	mx = max(mx, dlast[i] - dfirst[i - 1] - 1)
print(mx)


def solve():
	s1 = input()
	s2 = input()
	i = 0
	left = []
	for c in s2:
		while c != s1[i]:
			i += 1
		left.append(i)
		i += 1
	i = -1
	right = []
	for c in s2[::-1]:
		while c != s1[i]:
			i -= 1
		right.append(len(s1) + i)
		i -= 1
	right.reverse()
	mx = 0
	for i in range(len(s2) - 1):
		mx = max(mx, right[i + 1] - left[i] - 1)
	mx = max(mx, len(s1) - left[-1] - 1)
	mx = max(mx, right[0])
	print(mx)
for case in range(1):
	solve()


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def check(S, T):
	N = len(S)
	M = len(T)
	res = [N] * M
	i = j = 0
	while i < M:
		while j < N and T[i] != S[j]:
			j += 1
		res[i] = j
		j += 1
		i += 1
	return res
S = [ord(s) - 97 for s in input()]
T = [ord(t) - 97 for t in input()]
N = len(S)
M = len(T)
res1 = check(S, T)
res2 = check(S[::-1], T[::-1])
res2 = [N - a - 1 for a in res2[::-1]]
res1.insert(0, -1)
res2.append(N)
ans = 0
for i in range(M + 1):
	ans = max(ans, res2[i] - res1[i] - 1)
print(ans)


from sys import setcheckinterval, stdin
setcheckinterval(1000)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
s = input()
t = input()
n = len(s)
d1 = {}
d1[0] = -1
d2 = {}
d2[0] = n
l = len(t)
ch = 0
for i in range(n):
	if ch == l:
		break
	if s[i] == t[ch]:
		ch += 1
		d1[ch] = i
s = list(s)
s = s[::-1]
t = list(t)
t = t[::-1]
ch = 0
for i in range(n):
	if ch == l:
		break
	if s[i] == t[ch]:
		ch += 1
		d2[ch] = n - i - 1
ans = []
for i in range(l + 1):
	ans.append(d2[l - i] - d1[i])
print(max(ans) - 1)


s = input()
t = input()
ns = len(s)
nt = len(t)
ans = 0
found = 0
DP_left = [0] * ns
DP_left[0] = int(s[0] == t[0])
for i in range(1, ns):
	if DP_left[i - 1] < nt:
		DP_left[i] = DP_left[i - 1] + (s[i] == t[DP_left[i - 1]])
DP_right = [0] * ns
DP_right[-1] = int(s[-1] == t[-1])
for i in reversed(range(ns - 1)):
	if 0 <= nt - DP_right[i + 1] - 1 < nt:
		DP_right[i] = DP_right[i + 1] + (s[i] == t[nt - 1 - DP_right[i + 1]])
from collections import defaultdict
d_r = defaultdict(int)
d_l = defaultdict(int)
old = 1
for (index, i) in enumerate(DP_left):
	if i == old:
		d_l[i] = index
		old += 1
for (index, i) in enumerate(DP_right):
	d_r[i] = max(d_r[i], index)
for i in range(nt + 1):
	if i == 0:
		ans = max(ans, d_r[nt])
	elif i == nt:
		ans = max(ans, ns - d_l[nt] - 1)
	else:
		ans = max(ans, d_r[nt - i] - d_l[i] - 1)
print(ans)


import sys
from collections import defaultdict

def get_after(l, num):
	(low, high) = (0, len(l) - 1)
	ans = len(l)
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > num:
			ans = min(ans, mid)
			high = mid - 1
		else:
			low = mid + 1
	return l[ans]

def get_before(l, num):
	(low, high) = (0, len(l) - 1)
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		if l[mid] < num:
			ans = max(ans, mid)
			low = mid + 1
		else:
			high = mid - 1
	return l[ans]
dic = defaultdict(list)
s = sys.stdin.readline()[:-1]
t = sys.stdin.readline()[:-1]
n = len(s)
for i in range(n):
	dic[s[i]].append(i)
n = len(t)
l = [0 for _ in range(n + 2)]
l[0] = -1
l[-1] = len(s)
for i in range(n - 1, -1, -1):
	y = dic[t[i]][-1]
	if y < l[i + 2]:
		l[i + 1] = y
	else:
		y = get_before(dic[t[i]], l[i + 2])
		l[i + 1] = y
	last = l[i + 1]
ans = l[1] - l[0] - 1
for i in range(n):
	y = dic[t[i]][0]
	if y > l[i]:
		l[i + 1] = y
	else:
		y = get_after(dic[t[i]], l[i])
		l[i + 1] = y
	ans = max(ans, l[i + 2] - l[i + 1] - 1)
ans = max(ans, l[-1] - l[-2] - 1)
print(ans)


import math

def posible(str1, str2, mid, n, m, R):
	coun = 0
	cur = 0
	for i in range(n - mid + 1):
		rang = i + mid
		if cur + R[rang] >= m:
			return True
		if str1[i] == str2[cur]:
			cur += 1
	return False
str1 = input()
str2 = input()
n = len(str1)
m = len(str2)
R = []
r = m - 1
l = n - 1
coun = 0
for i in range(n):
	R.append(0)
R.append(0)
while l >= 0:
	if r >= 0 and str1[l] == str2[r]:
		r -= 1
		coun += 1
	R[l] = coun
	l -= 1
lo = 0
hi = n - 1
ans = 0
while lo <= hi:
	mid = math.floor((lo + hi) / 2)
	if posible(str1, str2, int(mid), n, m, R):
		ans = mid
		lo = mid + 1
	else:
		hi = mid - 1
print(ans)


s = input()
t = input()
fp = [-1]
tp = 0
for i in range(len(s)):
	if s[i] == t[tp]:
		fp.append(i)
		tp += 1
		if tp == len(t):
			break
lp = [len(s)]
tp = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == t[tp]:
		lp.append(i)
		tp -= 1
		if tp == -1:
			break
lp.reverse()
print(max([l - f for (l, f) in zip(lp, fp)]) - 1)


s = input()
t = input()
(n, m) = (len(s), len(t))
(i, j) = (0, 0)
first = []
last = []
while j < m:
	if s[i] == t[j]:
		first.append(i)
		i += 1
		j += 1
	else:
		i += 1
(i, j) = (n - 1, m - 1)
while j >= 0:
	if s[i] == t[j]:
		last.append(i)
		j -= 1
	i -= 1
last = last[::-1]
ans = max(last[0], n - first[-1] - 1)
for i in range(m - 1):
	ans = max(ans, last[i + 1] - first[i] - 1)
print(ans)


s = input()
t = input()
lastL = [0] * len(t)
lastR = [0] * len(t)
j = 0
for i in range(len(s)):
	if s[i] == t[j]:
		lastL[j] = i
		j += 1
	if j >= len(t):
		break
j = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == t[j]:
		lastR[j] = i
		j -= 1
	if j < 0:
		break
max_gap = max(lastR[0], len(s) - 1 - lastL[-1])
for i in range(len(t) - 1):
	max_gap = max(max_gap, lastR[i + 1] - 1 - lastL[i])
print(max_gap)


s1 = list(input())
r_s1 = s1[::-1]
s2 = list(input())
r_s2 = s2[::-1]
l1 = len(s1)
l2 = len(s2)
arr1 = []
arr2 = []
i = 0
j = 0
while i < l1 and j < l2:
	if s1[i] == s2[j]:
		arr1.append(i)
		j += 1
	i += 1
i = 0
j = 0
while i < l1 and j < l2:
	if r_s1[i] == r_s2[j]:
		arr2.append(l1 - 1 - i)
		j += 1
	i += 1
ans = 0
for i in range(1, l2):
	ans = max(ans, arr1[i] - arr1[i - 1] - 1)
	ans = max(ans, arr2[i - 1] - arr2[i] - 1)
for i in range(l2 - 1):
	ans = max(ans, arr2[l2 - 2 - i] - arr1[i] - 1)
ans = max(ans, l1 - arr1[-1] - 1, arr1[0])
ans = max(ans, arr2[-1], l1 - arr2[0] - 1)
print(ans)


a = input()
b = input()
n = len(a)
m = len(b)
i = 0
j = 0
(f, bb) = ([0] * m, [0] * m)
while j != m:
	if a[i] == b[j]:
		f[j] = i
		i += 1
		j += 1
	else:
		i += 1
i = 0
j = 0
while j != m:
	if a[n - 1 - i] == b[m - 1 - j]:
		bb[m - 1 - j] = n - 1 - i
		i += 1
		j += 1
	else:
		i += 1
ans = max(n - f[-1] - 1, bb[0])
for i in range(m - 1):
	ans = max(ans, bb[i + 1] - f[i] - 1)
print(ans)


import sys, math, bisect
from collections import defaultdict
M = 10 ** 9 + 7

def pow(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res *= a
		a *= a
		b >>= 1
	return res

def powmod(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a *= a
		b >>= 1
	return res

def inv(a, m):
	return powmod(a, m - 2, m)

def factor(n):
	potentional_p = 3
	itog_list = {}
	if n % 2 == 0:
		itog_list[2] = 0
	while n % 2 == 0:
		n = n // 2
		itog_list[2] += 1
	while n - 1:
		if potentional_p > n ** 0.5:
			if n in itog_list:
				itog_list[n] += 1
			else:
				itog_list[n] = 1
			return itog_list
		while n % potentional_p == 0:
			n = n // potentional_p
			if potentional_p in itog_list:
				itog_list[potentional_p] += 1
			else:
				itog_list[potentional_p] = 1
		potentional_p += 2
	return itog_list
s = input()
t = input()
forward = []
backward = []
rptr = 0
for i in range(len(s)):
	if rptr == len(t):
		break
	if s[i] == t[rptr]:
		forward.append(i)
		rptr += 1
rptr = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if rptr == -1:
		break
	if s[i] == t[rptr]:
		backward.append(i)
		rptr -= 1
backward = backward[::-1]
backward.append(forward[-1])
mx = max(forward[0], len(s) - 1 - backward[-2], len(s) - 1 - forward[-1], backward[0])
for i in range(len(t)):
	mx = max(mx, backward[i + 1] - forward[i] - 1)
print(mx)


s = input()
t = input()
left = [-1]
rightReversed = [len(s)]
i = 0
for x in range(len(s)):
	if t[i] == s[x]:
		left.append(x)
		i += 1
	if i >= len(t):
		break
i = len(t) - 1
for x in range(len(s) - 1, -1, -1):
	if t[i] == s[x]:
		rightReversed.append(x)
		i -= 1
	if i < 0:
		break
right = rightReversed[::-1]
maxN = 0
for x in range(len(t) + 1):
	maxN = max(right[x] - left[x], maxN)
print(maxN - 1)


s = input().rstrip()
t = input().rstrip()
left = []
idx = 0
for (i, item) in enumerate(s):
	if item == t[idx]:
		left.append(i)
		idx += 1
	if idx == len(t):
		break
right = []
idx = len(t) - 1
for (i, item) in enumerate(s[::-1]):
	if item == t[idx]:
		right.append(len(s) - i - 1)
		idx -= 1
	if idx == -1:
		break
right.reverse()
ans = max(right[0], len(s) - right[-1] - 1)
ans = max(ans, left[0], len(s) - left[-1] - 1)
for (l, r) in zip(left, right[1:]):
	ans = max(ans, r - l - 1)
print(ans)


def f(s, t):
	right = [0] * len(t)
	for i in reversed(range(len(t))):
		pos = len(s) - 1
		if i + 1 < len(t):
			pos = right[i + 1] - 1
		while s[pos] != t[i]:
			pos -= 1
		right[i] = pos
	ans = 0
	pos = 0
	for i in range(len(s)):
		rpos = len(s) - 1
		if pos < len(t):
			rpos = right[pos] - 1
		ans = max(ans, rpos - i + 1)
		if pos < len(t) and t[pos] == s[i]:
			pos += 1
	return ans
s = input()
t = input()
print(f(s, t))


l1 = [i for i in input()]
l2 = [i for i in input()]
length1 = len(l1)
length2 = len(l2)
ij = 0
ji = len(l2) - 1
count1 = []
count2 = []
for i in range(length1):
	if ij < length2:
		if l1[i] == l2[ij]:
			ij += 1
			count1.append(i)
	if ji >= 0:
		if l1[-i - 1] == l2[ji]:
			ji -= 1
			count2.append(length1 - i - 1)
	if ij == length2 and ji == -1:
		break
final = [count2[len(count2) - 1 - 0]]
for i in range(length2 - 1):
	x = count2[-i - 2] - count1[i] - 1
	if x > final[0]:
		final[0] = x
print(max(final[0], length1 - 1 - count1[len(count1) - 1]))


s = input()
t = input()
(sl, tl) = (len(s), len(t))
left = []
right = []
x = 0
for i in range(sl):
	if x < tl and s[i] == t[x]:
		left.append(i)
		x += 1
x = tl - 1
for i in range(sl - 1, -1, -1):
	if x >= 0 and s[i] == t[x]:
		right.append(i)
		x -= 1
right.reverse()
if tl == 1:
	print(max(max(left[0], sl - left[0] - 1), max(right[0], sl - right[0] - 1)))
else:
	ans = max(sl - left[-1] - 1, right[0])
	for i in range(1, tl):
		ans = max(ans, right[i] - left[i - 1] - 1)
	print(ans)


def f(n):
	for i in range(-1, lt):
		if right[i + 1] - left[i] > n:
			return True
	return False
s = input()
t = input()
ls = len(s)
lt = len(t)
right = dict()
left = dict()
i = 0
j = 0
ls = len(s)
left[-1] = -1
while i < lt:
	if s[j] == t[i]:
		left[i] = j
		i += 1
	j += 1
j = ls - 1
i = lt - 1
right[lt] = ls
while i >= 0:
	if s[j] == t[i]:
		right[i] = j
		i -= 1
	j -= 1
low = 0
high = ls - 1
while low <= high:
	mid = (high + low) // 2
	if f(mid):
		low = mid + 1
	else:
		high = mid - 1
print(high)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

def solve(S, T):
	(N, M) = (len(S), len(T))
	left = [-1 for _ in range(N)]
	(si, ti) = (0, 0)
	while si < N:
		if ti >= M:
			left[si] = left[si - 1]
			si += 1
			continue
		if S[si] == T[ti]:
			left[si] = ti
			ti += 1
		else:
			left[si] = left[si - 1] if si > 0 else -1
		si += 1
	right = [M for _ in range(N)]
	(si, ti) = (N - 1, M - 1)
	while si >= 0:
		if ti < 0:
			right[si] = right[si + 1]
			si -= 1
			continue
		if S[si] == T[ti]:
			right[si] = ti
			ti -= 1
		else:
			right[si] = right[si + 1] if si + 1 < N else M
		si -= 1
	ans = 0
	for i in range(N):
		if left[i] >= M - 1:
			ans = max(ans, N - i - 1)
			break
		j = bisect.bisect_right(right, left[i] + 1)
		ans = max(ans, j - i - (2 if left[i] >= 0 else 1))
	print(ans)
S = input()
T = input()
solve(S, T)


from collections import defaultdict
s = input()
t = input()
prev = defaultdict(lambda : -1)
next_i = [-1] * len(s)
for (i, c) in enumerate(s):
	if prev[c] != -1:
		next_i[prev[c]] = i
	prev[c] = i
pos = [-1] + [0] * len(t) + [len(s)]
i = 0
for (j, c) in enumerate(t, start=1):
	while s[i] != c:
		i += 1
	pos[j] = i
	i += 1
ans = 0
for i in range(len(t), 0, -1):
	ans = max(ans, pos[i + 1] - pos[i] - 1)
	while next_i[pos[i]] != -1 and next_i[pos[i]] < pos[i + 1]:
		pos[i] = next_i[pos[i]]
	ans = max(ans, pos[i] - pos[i - 1] - 1)
print(ans)


s = input()
t = input()
j = len(t) - 1
last = [None] * len(t)
for _i in range(len(s)):
	i = len(s) - _i - 1
	if j >= 0 and s[i] == t[j]:
		last[j] = i
		j -= 1
answer = -1
j = 0
first = [None] * len(t)
for i in range(len(s)):
	if j < len(t):
		if s[i] == t[j]:
			first[j] = i
			if j > 0:
				answer = max(answer, last[j] - first[j - 1] - 1)
			else:
				answer = last[j]
			j += 1
	else:
		break
answer = max(answer, len(s) - 1 - first[-1])
print(answer)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 10 ** 9 + 7

def solve():
	(S, T) = (getStr(), getStr())
	(N, M) = (len(S), len(T))
	(left, right) = ([-1], [N])
	j = 0
	for i in range(N):
		if S[i] == T[j]:
			left.append(i)
			j += 1
		if j == M:
			break
	left.append(N)
	j = M - 1
	for i in range(N - 1, -1, -1):
		if S[i] == T[j]:
			right.append(i)
			j -= 1
		if j == -1:
			break
	right.append(-1)
	right.reverse()
	ans = 0
	for i in range(len(left) - 1):
		ans = max(ans, right[i + 1] - left[i] - 1)
	return ans
print(solve())


string = str(input())
substring = str(input())
len_string = len(string)
len_substring = len(substring)
minimal_string_pos = []
max_string_pos = []
sub_flag = 0
for i in range(len_string):
	if string[i] == substring[sub_flag]:
		minimal_string_pos.append(i)
		sub_flag += 1
		if sub_flag > len_substring - 1:
			break
sub_flag = len(substring) - 1
for i in range(len_string - 1, -1, -1):
	if string[i] == substring[sub_flag]:
		max_string_pos.append(i)
		sub_flag -= 1
		if sub_flag < 0:
			break
max_string_pos = max_string_pos[::-1]
digit_max_1 = max(max_string_pos[0], len_string - minimal_string_pos[len(minimal_string_pos) - 1] - 1)
digit_max_2 = 0
for i in range(len(substring) - 1):
	digit_max_2 = max_string_pos[i + 1] - minimal_string_pos[i] - 1 if max_string_pos[i + 1] - minimal_string_pos[i] - 1 > digit_max_2 else digit_max_2
print(max(digit_max_1, digit_max_2))


import sys
in_file = sys.stdin
s = in_file.readline().strip()
t = in_file.readline().strip()
L = [0]
l = 0
R = [0]
r = len(t) - 1
for i in range(len(s)):
	if l < len(t) and s[i] == t[l]:
		l += 1
	L.append(l)
	if r >= 0 and s[len(s) - i - 1] == t[r]:
		r -= 1
	R.append(len(t) - r - 1)
Lc = [-1 for i in range(len(t) + 1)]
Rc = [-1 for i in range(len(t) + 1)]
for i in range(len(L)):
	if Lc[L[i]] == -1:
		Lc[L[i]] = i
	if Rc[R[i]] == -1:
		Rc[R[i]] = i
res = len(s)
for i in range(len(t) + 1):
	j = len(t) - i
	if Rc[j] + Lc[i] < res:
		res = Rc[j] + Lc[i]
sys.stdout.write(str(len(s) - res))
sys.stdout.flush()


s = input()
t = input()
lefts = [0 for i in range(len(t))]
rights = [0 for i in range(len(t))]
i = 0
j = 0
while i < len(s) and j < len(t):
	if s[i] == t[j]:
		lefts[j] = i
		j += 1
	i += 1
i = len(s) - 1
j = len(t) - 1
while i >= 0 and j >= 0:
	if s[i] == t[j]:
		rights[j] = i
		j -= 1
	i -= 1
ans = max(len(s) - lefts[-1] - 1, rights[0])
for i in range(len(t) - 1):
	ans = max(ans, rights[i + 1] - lefts[i] - 1)
print(ans)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
s = str(rd().strip())
t = str(rd().strip())
s = '0' + s
canl = [0] * (len(s) + 10)
canr = [0] * (len(s) + 10)
j = 0
for (i, v) in enumerate(s):
	if j < len(t) and v == t[j]:
		j += 1
	canl[i] = j
j = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if j >= 0 and s[i] == t[j]:
		j -= 1
	canr[i] = len(t) - j - 1

def check(x):
	if x > len(s):
		return False
	for i in range(1, len(s) - x + 1):
		l = i - 1
		r = i + x
		if canl[l] + canr[r] >= len(t):
			return True
	return False
l = 0
r = len(s)
while l < r:
	mid = (l + r) // 2
	if check(mid):
		l = mid + 1
	else:
		r = mid
print(r - 1)


s = input()
t = input()
n = len(s)
m = len(t)
dp1 = [0] * (n + 1)
for i in range(n):
	dp1[i + 1] = dp1[i]
	if dp1[i] < m and s[i] == t[dp1[i]]:
		dp1[i + 1] += 1
dp2 = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	dp2[i] = dp2[i + 1]
	if dp2[i + 1] < m and s[i] == t[-1 - dp2[i + 1]]:
		dp2[i] += 1

def check(ln):
	for i in range(n - ln + 1):
		if dp1[i] + dp2[i + ln] >= m:
			return True
	return False
(l, r) = (0, n)
while r - l > 1:
	mid = (l + r) // 2
	if check(mid):
		l = mid
	else:
		r = mid
print(l)


def solver():
	s = input().strip()
	t = input().strip()
	left = [len(s)] * len(t)
	right = [-1] * len(t)
	cnt = 0
	for i in range(len(t)):
		while s[cnt] != t[i]:
			cnt += 1
		left[i] = cnt
		cnt += 1
	cnt = len(s) - 1
	for i in range(len(t) - 1, -1, -1):
		while s[cnt] != t[i]:
			cnt -= 1
		right[i] = cnt
		cnt -= 1
	ans = max(len(s) - left[-1] - 1, right[0])
	for i in range(len(t) - 1):
		ans = max(ans, right[i + 1] - left[i] - 1)
	print(ans)

def main():
	while 1:
		try:
			solver()
		except EOFError:
			break
main()


s = input()
t = input()
L1 = []
L2 = []
ptr = 0
for i in range(0, len(s)):
	if s[i] == t[ptr]:
		L1.append(i)
		ptr += 1
	if ptr >= len(t):
		break
ptr = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == t[ptr]:
		L2.append(i)
		ptr -= 1
	if ptr < 0:
		break
L2 = L2[::-1]
mx = -1
for i in range(0, len(L1) - 1):
	mx = max(mx, L2[i + 1] - L1[i] - 1)
mx = max(mx, L2[0])
mx = max(mx, len(s) - L1[-1] - 1)
print(mx)


import sys
input = sys.stdin.readline
s = input()
t = input()
(l, r) = ([0] * len(t), [0] * len(t))
(li, ri) = (0, len(s) - 1)
for i in range(len(t)):
	while s[li] != t[i]:
		li += 1
	while s[ri] != t[-i - 1]:
		ri -= 1
	l[i] = li
	r[-i - 1] = ri
	li += 1
	ri -= 1
print(max([r[0], len(s) - l[-1] - 1] + [max(0, r[i] - l[i - 1]) - 1 for i in range(1, len(t))]))


from collections import defaultdict as DD
from bisect import bisect_left as BL
from bisect import bisect_right as BR
from itertools import combinations as IC
from itertools import permutations as IP
from random import randint as RI
import sys
import math
MOD = pow(10, 9) + 7
from math import gcd

def IN(f=0):
	if f == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
a = input()
b = input()
n = len(a)
m = len(b)
q = []
w = []
j = 0
d1 = DD(int)
d2 = DD(int)
for i in range(len(a)):
	if j >= len(b):
		q.append(0)
	elif a[i] == b[j]:
		q.append(j + 1)
		j += 1
	else:
		q.append(0)
j = len(b) - 1
for i in range(len(a) - 1, -1, -1):
	if j < 0:
		w.append(0)
	elif a[i] == b[j]:
		w.append(j + 1)
		j -= 1
	else:
		w.append(0)
w.reverse()
for i in range(len(a)):
	d1[q[i]] = i + 1
for i in range(len(a)):
	d2[w[i]] = i + 1
ans = max(d2[1] - 1, len(a) - d1[len(b)])
for i in range(1, m):
	tr = abs(d1[i] - d2[i + 1]) - 1
	if ans < tr:
		ans = tr
print(ans)


s = input()
t = input()
forward = []
backward = []
rptr = 0
for i in range(len(s)):
	if rptr == len(t):
		break
	if s[i] == t[rptr]:
		forward.append(i)
		rptr += 1
rptr = len(t) - 1
for i in range(len(s) - 1, -1, -1):
	if rptr == -1:
		break
	if s[i] == t[rptr]:
		backward.append(i)
		rptr -= 1
backward = backward[::-1]
backward.append(forward[-1])
mx = max(forward[0], len(s) - 1 - backward[-2], len(s) - 1 - forward[-1], backward[0])
for i in range(len(t)):
	mx = max(mx, abs(forward[i] - backward[i + 1]) - 1)
print(mx)


s = input()
t = input()
ar1 = []
i = 0
for j in range(len(s)):
	if i < len(t) and s[j] == t[i]:
		ar1.append(j)
		i += 1
i = len(t) - 1
ar2 = [0] * len(t)
j = len(s) - 1
while j >= 0:
	if i >= 0 and s[j] == t[i]:
		ar2[i] = j
		i -= 1
	j -= 1
ans = ar1[0]
ans = max(ans, ar2[0])
ans = max(ans, len(s) - ar1[-1] - 1)
ans = max(ans, len(s) - ar2[-1] - 1)
for i in range(len(t) - 1):
	ans = max(ans, ar2[i + 1] - ar1[i] - 1)
print(ans)


s = input()
t = input()
n = len(s)
m = len(t)
le = []
ri = []
ans = 0
p = 0
for i in range(n):
	if p < m:
		if s[i] == t[p]:
			le.append(i)
			if p == m - 1:
				ans = max(ans, n - 1 - i)
			p += 1
p = m - 1
for j in range(n - 1, -1, -1):
	if p >= 0:
		if s[j] == t[p]:
			ri.append(j)
			if p == 0:
				ans = max(ans, j - 0)
			p -= 1
ri.reverse()
for k in range(m - 1):
	ans = max(ans, ri[k + 1] - le[k] - 1)
print(ans)


from sys import stdin, stdout
import math
from math import gcd, sqrt
s1 = input()
N = len(s1)
s2 = input()
M = len(s2)
asc = []
dsc = []
k = 0
for i in range(len(s1)):
	if s1[i] == s2[k]:
		asc.append(i)
		k += 1
	if k == M:
		break
k = M - 1
for i in range(len(s1) - 1, -1, -1):
	if s1[i] == s2[k]:
		dsc.append(i)
		k -= 1
	if k == -1:
		break
dsc = dsc[::-1]
res = 0
for i in range(M - 1):
	d = dsc[i + 1] - asc[i] - 1
	res = max(d, res)
res = max(res, asc[0])
res = max(res, dsc[0])
res = max(res, N - 1 - asc[-1])
res = max(res, N - 1 - dsc[-1])
print(res)


s = input()
t = input()
n = len(s)
m = len(t)
l = [-1]
r = [n]
c = 0
for i in range(n):
	if s[i] == t[c]:
		l.append(i)
		c += 1
		if c >= m:
			break
c = 0
for i in range(n):
	if s[-1 - i] == t[-1 - c]:
		r.append(n - 1 - i)
		c += 1
		if c >= m:
			break
mx = 0
for i in range(m + 1):
	mx = max(mx, r[m - i] - l[i] - 1)
print(mx)


s = str(input())
t = str(input())
i = 0
j = 0
arr1 = []
while i < len(s):
	if s[i] == t[j]:
		arr1.append(i + 1)
		j += 1
	i += 1
	if j == len(t):
		break
i = len(s) - 1
j = len(t) - 1
arr2 = [0] * len(t)
while i >= 0:
	if s[i] == t[j]:
		arr2[j] = i + 1
		j -= 1
	i -= 1
	if j == -1:
		break
ans = max(arr2[0] - 1, len(s) - arr1[-1])
for i in range(len(t) - 1):
	ans = max(ans, arr2[i + 1] - arr1[i] - 1)
print(ans)


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def display_2D_list(li):
	for i in li:
		print(i)

def prefix_sum(li):
	sm = 0
	res = []
	for i in li:
		sm += i
		res.append(sm)
	return res

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = False
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False

def main():
	st = list(stdin.readline().strip())
	search = list(stdin.readline().strip())
	pos = len(search) - 1
	back = [0 for _ in range(len(search))]
	for (index, i) in reversed(list(enumerate(st))):
		if i == search[pos]:
			back[pos] = index
			pos -= 1
			if pos == -1:
				break
	pos = 0
	maxi = 0
	for (i, ele) in enumerate(st):
		if pos == len(search):
			k = len(st) - i
		else:
			k = back[pos] - i
		maxi = max(maxi, k)
		if pos < len(search) and ele == search[pos]:
			pos = pos + 1
	print(maxi)
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


s = input()
a = input()
i = 0
l = []
r = []
for j in a:
	while s[i] != j:
		i += 1
	l.append(i)
	i += 1
i = len(s) - 1
for j in a[::-1]:
	while s[i] != j:
		i -= 1
	r.append(i)
	i -= 1
r.reverse()
ans = r[0]
for i in range(len(a) - 1):
	ans = max(ans, r[i + 1] - l[i] - 1)
ans = max(ans, len(s) - l[-1] - 1)
print(ans)


import sys
input = sys.stdin.readline
s = list(input().rstrip())
t = list(input().rstrip())
(n, m) = (len(s), len(t))
j = 0
(l, r) = ([-1] * m, [-1] * m)
for i in range(n):
	if s[i] == t[j]:
		l[j] = i
		j += 1
	if j == m:
		break
j = m - 1
for i in range(n - 1, -1, -1):
	if s[i] == t[j]:
		r[j] = i
		j -= 1
	if j == -1:
		break
ans = max(n - l[-1] - 1, r[0])
for i in range(m - 1):
	ans = max(ans, r[i + 1] - l[i] - 1)
print(ans)