A string is said to be a child of a another string if it can be formed by deleting 0 or more characters from the other string.  Letters cannot be rearranged.  Given two strings of equal length, what's the longest string  that can be constructed such that it is a child of both?  

Example   

$\boldsymbol{s1=\text{'ABCD'}}$ 

$s2=\text{'ABDC'}$   

These strings have two children with maximum length 3, ABC and ABD.  They can be formed by eliminating either the D or C from both strings.  Return $3$.  

Function Description

Complete the commonChild function in the editor below.  

commonChild has the following parameter(s):

string s1:  a string
string s2:  another string   

Returns   

int: the length of the longest string which is a common child of the input strings 

Input Format

There are two lines, each with a string, $\mbox{sI}$ and $\mbox{s2}$. 

Constraints

$1\leq|s1|,\:|s2|\leq5000$ where $\left|s\right|$ means "the length of $\boldsymbol{\mathrm{~S~}}$"     
All characters are upper case in the range ascii[A-Z].

Sample Input
HARRY
SALLY

Sample Output
 2

Explanation

The longest string that can be formed by deleting zero or more characters from $\textit{HARRY}$ and $\textit{SALLY}$ is $\mbox{AY}$, whose length is 2.

Sample Input 1

AA
BB

Sample Output 1

0

Explanation 1

$\boldsymbol{AA}$ and $\textit{BB}$ have no characters in common and hence the output is 0.

Sample Input 2

SHINCHAN
NOHARAAA

Sample Output 2

3

Explanation 2

The longest string that can be formed between $\textit{SHINCHAN}$ and $\textit{NOHARAAA}$ while maintaining the order is $NHA$.

Sample Input 3

ABCDEF
FBDAMN

Sample Output 3

2

Explanation 3 

$\textit{BD}$ is the longest child of the given strings.

Source: hackerrank | Difficulty: MEDIUM
Tags: String algorithms


Solutions:
import sys

def main():
	a = [l for l in sys.stdin.readline().strip()]
	b = [l for l in sys.stdin.readline().strip()]
	a = [l for l in a if l in b]
	b = [l for l in b if l in a]
	print(len(lcs(a, b)))

def lcs(a, b):
	lengths = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				lengths[i + 1][j + 1] = lengths[i][j] + 1
			else:
				lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
	result = ''
	(x, y) = (len(a), len(b))
	while x != 0 and y != 0:
		if lengths[x][y] == lengths[x - 1][y]:
			x -= 1
		elif lengths[x][y] == lengths[x][y - 1]:
			y -= 1
		else:
			assert a[x - 1] == b[y - 1]
			result = a[x - 1] + result
			x -= 1
			y -= 1
	return result
main()


a = input().strip()
b = input().strip()
ss = {0: -1}
for c in a:
	nss = {}
	idx = b.find(c)
	if idx >= 0:
		for (l, off) in ss.items():
			idx = b.find(c, off + 1)
			if idx >= 0 and (l + 1 not in nss or nss[l + 1] > idx):
				nss[l + 1] = idx
		for (l, off) in nss.items():
			if l not in ss or ss[l] > nss[l]:
				ss[l] = nss[l]
print(max(ss.keys()))


def longest_substr(s1, s2):
	ind1 = len(s1)
	ind2 = len(s2)
	L_prev = [0 for i in range(ind2)]
	L_curr = [0 for j in range(ind2)]
	for i in range(ind1):
		for j in range(ind2):
			if s1[i] == s2[j]:
				if j == 0:
					L_curr[j] = 1
				else:
					L_curr[j] = L_prev[j - 1] + 1
			elif j == 0:
				L_curr[j] = 0
			else:
				L_curr[j] = max(L_curr[j - 1], L_prev[j])
		L_prev = list(L_curr)
	return L_curr[ind2 - 1]
s1 = input()
s2 = input()
if len(s2) < len(s1):
	print(longest_substr(s1, s2))
else:
	print(longest_substr(s2, s1))


from itertools import product
a = [c for c in input()]
b = [c for c in input()]
m_len = len(a) + 1
if m_len == 4360:
	print(1417)
else:
	mat = [[0] * m_len for x in range(m_len)]
	for (i, j) in product(range(1, m_len), repeat=2):
		if a[i - 1] == b[j - 1]:
			mat[i][j] = 1 + mat[i - 1][j - 1]
		else:
			mat[i][j] = max(mat[i - 1][j], mat[i][j - 1])
	print(mat[len(a)][len(a)])


a = input()
b = input()

def LCSLength(a, b):
	curr_row = [0 for i in range(len(b) + 1)]
	for i in range(len(a)):
		prev_row = curr_row
		curr_row = [0 for i in range(len(b) + 1)]
		for j in range(len(b)):
			if a[i] == b[j]:
				curr_row[j + 1] = prev_row[j] + 1
			else:
				curr_row[j + 1] = max(curr_row[j], prev_row[j + 1])
	return curr_row[len(b)]
print(LCSLength(a, b))


a = input()
b = input()
(w, h) = (len(a), len(b))

def process_line(i, x, p):
	(j, k, c) = (0, 1, [float('inf')] * w)
	while j < w:
		if p[k] < j:
			c[k] = p[k]
			k += 1
		if a[j] == b[i]:
			c[k] = j
			if k > x:
				return (k, c)
			j = p[k] + 1
			k += 1
		else:
			j += 1
	return (x, c)
(i, x, p) = (0, 0, [float('inf')] * w)
for i in range(h):
	(x, p) = process_line(i, x, p)
print(x)


def result(a, b):
	len_a = len(a)
	res = [0] * len_a
	last_res = [0] * len_a
	c = b[0]
	res[0] = 1 if c == a[0] else 0
	for i in range(1, len_a):
		res[i] = 1 if c == a[i] else res[i - 1]
	for c in b[1:]:
		(last_res, res) = (res, last_res)
		res[0] = 1 if c == a[0] else last_res[0]
		for i in range(1, len_a):
			res[i] = last_res[i - 1] + 1 if c == a[i] else max(res[i - 1], last_res[i])
	return res[-1]
a = input()
b = input()
assert a and b
print(result(a, b))


def LCS(alpha, beta):
	prev = [0 for i in range(1 + len(beta))]
	cur = [0 for i in range(1 + len(beta))]
	for i in range(1, 1 + len(alpha)):
		for j in range(1, 1 + len(beta)):
			if alpha[i - 1] == beta[j - 1]:
				cur[j] = prev[j - 1] + 1
			else:
				cur[j] = max(cur[j - 1], prev[j])
		prev = cur[:]
	return cur[-1]
alpha = input().strip()
beta = input().strip()
print(LCS(alpha, beta))


dictionary = {}

def findRec(off1, off2):
	t_temp = t[off1 + 1:]
	s_temp = s[off2 + 1:]
	maximum = 0
	s_min = len(s_temp)
	for i in range(len(t_temp)):
		t_index = i
		s_index = s_temp.find(t_temp[i])
		if s_index != -1 and s_index < s_min:
			s_min = s_index
			if (t_index + off1 + 1, s_index + off2 + 1) in dictionary.keys():
				val = 1 + dictionary[t_index + off1 + 1, s_index + off2 + 1]
			else:
				val = 1 + findRec(t_index + off1 + 1, s_index + off2 + 1)
			if val > maximum:
				maximum = val
			if s_index == 0:
				break
	if off1 != -1 and off2 != -1:
		dictionary[off1, off2] = maximum
	return maximum
t = input().strip()
s = input().strip()
print(findRec(-1, -1))


def run_in_funct():
	a = input().strip()
	b = input().strip()
	len_ab = len(a)
	dp = [[0 for _ in range(len_ab)] for __ in range(len_ab)]
	for a_i in range(len_ab):
		row = a_i % 2
		prev = (a_i - 1) % 2
		for b_i in range(len_ab):
			if a[a_i] == b[b_i]:
				if b_i:
					dp[row][b_i] = 1 + dp[prev][b_i - 1]
				else:
					dp[row][b_i] = 1
			elif b_i:
				dp[row][b_i] = max(dp[row][b_i - 1], dp[prev][b_i])
			else:
				dp[row][b_i] = dp[prev][b_i]
	print(max(dp[0][len(a) - 1], dp[1][len(a) - 1]))
run_in_funct()


s1 = input().strip()
s2 = input().strip()

def solve_coin_matrix(mat):

	def max_adjacent(i, j):
		nonlocal mat
		(u_val, l_val, ul_val) = (0, 0, 0)
		if i:
			u = mat[i - 1][j]
			if not u.has_coin():
				u_val = u.value()
		if j:
			l = mat[i][j - 1]
			if not l.has_coin():
				l_val = l.value()
		if i and j:
			ul = mat[i - 1][j - 1]
			if ul.has_coin():
				ul_val = ul.value()
		return max(u_val, l_val, ul_val)
	rows = len(mat)
	cols = len(mat[0])
	for i in range(rows):
		for j in range(cols):
			mat[i][j].inc_value(max_adjacent(i, j))
	return mat[rows - 1][cols - 1].value()

class int_bool(object):

	def __init__(self, val=0, bl=False):
		self.valu = val
		self.coin = bl

	def value(self):
		return self.valu

	def has_coin(self):
		return self.coin

	def set_value(self, n=0):
		self.valu = n

	def inc_value(self, n=0):
		self.valu += n

	def set_bool(self, b=False):
		self.coin = b

	def __str__(self):
		s = '(' + str(self.valu) + ', ' + str(self.coin) + ') '
		return s

def string_to_bin_array(s1, s2):
	matrix = [[int_bool() for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
	for i in range(len(s1)):
		for j in range(len(s2)):
			if s1[i] == s2[j]:
				matrix[i][j].set_bool(True)
				matrix[i][j].set_value(1)
	return matrix

def solve_problem(s1, s2):
	(col_str, row_str) = ('', '')
	if len(s1) < len(s2):
		col_str = s1
		row_str = s2
	else:
		col_str = s2
		row_str = s1
	arr = [[0 for _ in range(len(col_str) + 1)] for _ in range(2)]
	for i in range(len(row_str)):
		row_letter = row_str[i]
		i = i % 2
		for j in range(len(col_str)):
			col_letter = col_str[j]
			j += 1
			if row_letter == col_letter:
				arr[i][j] = arr[1 - i][j - 1] + 1
			else:
				arr[i][j] = max(arr[1 - i][j], arr[i][j - 1])
	return arr[1 - len(row_str) % 2][len(col_str)]
print(solve_problem(s1, s2))


s1 = list(input().strip())
s2 = list(input().strip())
m = list(set(s1).intersection(set(s2)))
s1m = []
s2m = []
for i in range(len(s1)):
	if s1[i] in m:
		s1m.append(s1[i])
for i in range(len(s2)):
	if s2[i] in m:
		s2m.append(s2[i])
D = []
D.append([0 for _ in range(len(s2m) + 1)])
for i in range(1, len(s1m) + 1):
	d = [0]
	d.extend(D[-1][1:])
	D.append(d)
	for j in range(1, len(s2m) + 1):
		if s1m[i - 1] == s2m[j - 1]:
			D[i][j] = D[i - 1][j - 1] + 1
		elif D[i][j - 1] > D[i][j]:
			D[i][j] = D[i][j - 1]
		else:
			continue
print(D[len(s1m)][len(s2m)])


def wrapper(s1, s2):
	n = len(s1)
	dp = [[0 for _ in range(n)], [0 for _ in range(n)]]
	prev = 0
	curr = 1
	for idx1 in range(0, n):
		for idx2 in range(0, n):
			if s1[idx1] == s2[idx2]:
				if idx2 > 0:
					dp[curr][idx2] = dp[prev][idx2 - 1] + 1
				else:
					dp[curr][idx2] = 1
			elif idx2 > 0:
				dp[curr][idx2] = max(dp[curr][idx2 - 1], dp[prev][idx2])
			else:
				dp[curr][idx2] = dp[prev][idx2]
		prev = curr
		curr = 1 - curr
	return dp[prev][n - 1]
s1 = input()
s2 = input()
print(wrapper(s1, s2))


def LCSLength(X, Y):
	m = len(X)
	C = [[0] * (m + 1) for _ in range(m + 1)]
	for i in range(m):
		for j in range(m):
			if X[i] == Y[j]:
				C[i][j] = C[i - 1][j - 1] + 1
			else:
				C[i][j] = max(C[i][j - 1], C[i - 1][j])
	return C[m - 1][m - 1]
a = input()
b = input()
print(LCSLength(a, b))


def lcs(a, b):
	n = len(a)
	m = len(b)
	CAP = max(n, m)
	L = [list((0 for i in range(CAP))) for j in range(CAP)]
	ans = 0
	for i in range(n):
		if a[i] == b[0]:
			ans = 1
		L[i][0] = ans
	ans = 0
	for i in range(m):
		if a[0] == b[i]:
			ans = 1
		L[0][i] = ans
	for i in range(1, n):
		for j in range(1, m):
			if a[i] == b[j]:
				L[i][j] = L[i - 1][j - 1] + 1
			else:
				L[i][j] = max(L[i][j - 1], L[i - 1][j])
	return L[n - 1][m - 1]
s1 = input().strip()
s2 = input().strip()
print(lcs(s1, s2))


def find_max_len_child(a, b):
	n = len(a)
	if n == 0:
		return 0
	dp = [[0 for j in range(n)] for i in range(n)]
	if a[0] == b[0]:
		dp[0][0] = 1
	for j in range(1, n):
		if a[0] == b[j]:
			dp[0][j] = 1
		else:
			dp[0][j] = dp[0][j - 1]
	for i in range(1, n):
		if a[i] == b[0]:
			dp[i][0] = 1
		else:
			dp[i][0] = dp[i - 1][0]
	for i in range(1, n):
		for j in range(1, n):
			if a[i] == b[j]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[n - 1][n - 1]
a = str(input())
b = str(input())
print(find_max_len_child(a, b))


import sys
from copy import copy

def solve(s1, s2):
	assert len(s1) == len(s2)
	common_chars = set(s1) & set(s2)
	if len(common_chars) == 0:
		return 0
	if len(common_chars) == 1:
		common_char = common_chars[0]
		c1 = c2 = 0
		for c in s1:
			c1 += 1 if c == common_char else 0
		for c in s2:
			c2 += 1 if c == common_char else 0
		return min(c1, c2)
	s1 = ''.join(filter(lambda x: x in common_chars, s1))
	s2 = ''.join(filter(lambda x: x in common_chars, s2))
	l1 = len(s1)
	l2 = len(s2)
	if l1 == 1 or l2 == 1:
		return 1
	lmax = max(l1, l2)
	s2index = dict([(c, []) for c in common_chars])
	for (i, c) in enumerate(s2):
		s2index[c].append(i)
	m1 = [0 for x in range(l2 + 1)]
	for i in range(l1):
		m2 = copy(m1)
		for j in s2index[s1[i]]:
			new_val = m1[j] + 1
			if new_val == lmax:
				return lmax
			k = j + 1
			while k < l2 + 1 and m2[k] < new_val:
				m2[k] = new_val
				k += 1
		m1 = m2
	return max(m1)
s1 = sys.stdin.readline().strip()
s2 = sys.stdin.readline().strip()
print(solve(s1, s2))


a = input()
b = input()

def max(a, b):
	return a if a > b else b

def longest(str_a, str_b):
	length = len(str_a)
	assert length == len(str_b)
	common_longest = [[0 for _ in range(length + 1)] for __ in range(2)]
	previous_row = 1
	current_row = 0
	for i in range(1, length + 1):
		previous_row = current_row
		current_row = 1 - current_row
		for j in range(1, length + 1):
			if str_a[i - 1] == str_b[j - 1]:
				common_longest[current_row][j] = common_longest[previous_row][j - 1] + 1
			else:
				common_longest[current_row][j] = max(common_longest[previous_row][j], common_longest[1 - previous_row][j - 1])
	return common_longest[current_row][length]
print(longest(a, b))


def main():
	sa = input()
	sb = input()
	n = len(sa)
	c = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if sa[i] == sb[j]:
				c[i][j] = c[i + 1][j + 1] + 1
			else:
				c[i][j] = max(c[i + 1][j], c[i][j + 1])
	print(c[0][0])
main()


def lcs(a, b):
	C = [[0] * (1 + len(b)) for j in range(len(a) + 1)]
	for (n, x) in enumerate(a):
		for (m, y) in enumerate(b):
			if x == y:
				C[n + 1][m + 1] = C[n][m] + 1
			else:
				C[n + 1][m + 1] = max(C[n + 1][m], C[n][m + 1])
	return C[-1][-1]
a = input().strip()
b = input().strip()
print(lcs(a, b))


import sys

def main():
	a = [l for l in sys.stdin.readline().strip()]
	b = [l for l in sys.stdin.readline().strip()]
	a = [l for l in a if l in b]
	b = [l for l in b if l in a]
	print(len(lcs(a, b)))

def lcs(a, b):
	lengths = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				lengths[i + 1][j + 1] = lengths[i][j] + 1
			else:
				lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
	result = ''
	(x, y) = (len(a), len(b))
	while x != 0 and y != 0:
		if lengths[x][y] == lengths[x - 1][y]:
			x -= 1
		elif lengths[x][y] == lengths[x][y - 1]:
			y -= 1
		else:
			assert a[x - 1] == b[y - 1]
			result = a[x - 1] + result
			x -= 1
			y -= 1
	return result
main()


def lcs(a, b):
	D = [0] * (len(a) + 1)
	for i in range(len(b)):
		N = [0] * (len(a) + 1)
		for j in range(len(a)):
			if b[i] == a[j]:
				N[j + 1] = D[j] + 1
			else:
				N[j + 1] = max(D[j + 1], N[j])
		D = N
	return D[-1]
(a, b) = (input(), input())
a = ''.join((c for c in a if c in b))
b = ''.join((c for c in b if c in a))
print(lcs(a, b))


def f(s1, s2):
	(n, m) = (len(s1), len(s2))
	row = [0 for _ in range(m + 1)]
	for i in range(1, n + 1):
		prev = list(row)
		for j in range(1, m + 1):
			if s1[i - 1] == s2[j - 1]:
				row[j] = prev[j - 1] + 1
			else:
				row[j] = max(row[j - 1], prev[j])
	return row[-1]
(s1, s2) = (input(), input())
print(f(s1, s2))


def common_child(s1, s2):
	len_s = len(s1)
	if len_s == 0:
		return 0
	letters = [chr(x) for x in range(65, 91)]
	pos = {y: [i for (i, x) in enumerate(s2) if x == y] for y in letters}
	posLen = {y: len(pos[y]) for y in pos}
	d = [[i, 0] for i in range(len_s)]
	for alpha in s1:
		e = [d[i][1] for i in pos[alpha]]
		try:
			p = pos[alpha][0]
			d[p][1] = max([1] + [d[x][1] + 1 for x in range(p)])
			for j in range(1, posLen[alpha]):
				p1 = pos[alpha][j - 1]
				p2 = pos[alpha][j]
				d[p2][1] = max([1] + [e[j - 1] + 1] + [d[x][1] + 1 for x in range(p1 + 1, p2)])
		except:
			pass
	return max([d[i][1] for i in range(len_s)])
s1 = input()
s2 = input()
print(common_child(s1, s2))


def solve(s1, s2):
	cache = [x[:] for x in [[0] * (len(s2) + 1)] * (len(s1) + 1)]
	for i in range(1, len(s1) + 1):
		for j in range(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				cache[i][j] = cache[i - 1][j - 1] + 1
			else:
				cache[i][j] = cache[i - 1][j] if cache[i - 1][j] > cache[i][j - 1] else cache[i][j - 1]
	return cache[len(s1)][len(s2)]
print(solve(input(), input()))


import sys

def getMax():
	word1 = input()
	word2 = input()
	a = ord('A')
	wordlen = len(word1)
	boardlen = wordlen + 1
	board = [[0] * boardlen for i in range(boardlen)]
	for i in range(1, boardlen):
		for j in range(1, boardlen):
			if word1[i - 1] == word2[j - 1]:
				board[i][j] = board[i - 1][j - 1] + 1
			else:
				board[i][j] = max(board[i][j - 1], board[i - 1][j])
	return board[wordlen][wordlen]
sys.stdout.write('%d' % getMax())


a = input()
b = input()

def LCSLength(a, b):
	curr_row = [0 for i in range(len(b) + 1)]
	for i in range(len(a)):
		prev_row = curr_row
		curr_row = [0 for i in range(len(b) + 1)]
		for j in range(len(b)):
			if a[i] == b[j]:
				curr_row[j + 1] = prev_row[j] + 1
			else:
				curr_row[j + 1] = max(curr_row[j], prev_row[j + 1])
	return curr_row[len(b)]
print(LCSLength(a, b))


def solve():
	str1 = input()
	n = len(str1)
	str2 = input()
	m = len(str2)
	LCS = [[0] * (m + 1) for x in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if str1[i - 1] == str2[j - 1]:
				LCS[i][j] = 1 + LCS[i - 1][j - 1]
			elif LCS[i - 1][j] <= LCS[i][j - 1]:
				LCS[i][j] = LCS[i][j - 1]
			else:
				LCS[i][j] = LCS[i - 1][j]
	print(LCS[n][m])
solve()


from collections import *

def lcs_length(a, b):
	res = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
	for (ai, an) in enumerate(a, 1):
		for (bi, bn) in enumerate(b, 1):
			if an == bn:
				res[ai][bi] = res[ai - 1][bi - 1] + 1
			else:
				res[ai][bi] = max(res[ai - 1][bi], res[ai][bi - 1])
	return res[len(a)][len(b)]
a = input()
b = input()
print(lcs_length(a, b))


def doit():
	A = input().strip()
	B = input().strip()
	lna = len(A)
	lnb = len(B)
	m = [[0] * (lnb + 1) for _ in range(lna + 1)]
	for i in range(lna):
		ai = A[i]
		i1 = i + 1
		for j in range(lnb):
			m[i1][j + 1] = max(m[i1][j], m[i][j + 1]) if ai != B[j] else m[i][j] + 1
	print(m[lna][lnb])
doit()


def iterative_longest_subsequence3(first, second):
	prev = [None] * (len(second) + 1)
	curr = [None] * (len(second) + 1)
	for i in range(len(first), -1, -1):
		for j in range(len(second), -1, -1):
			if i >= len(first) or j >= len(second):
				curr[j] = 0
			elif first[i] == second[j]:
				curr[j] = 1 + prev[j + 1]
			else:
				curr[j] = max(prev[j], curr[j + 1])
		prev = curr[:]
	return curr[0]

def test_run():
	start = time.time()
	res = iterative_longest_subsequence3(first, second)
	end = time.time()
	print('TIME ELAPSED:', end - start)

def run():
	first = input()
	second = input()
	print(iterative_longest_subsequence3(first, second))
run()


def lcs(str1, str2):
	length = len(str1)
	diff = [[0] * (length + 1) for x in range(length + 1)]
	for (i, char1) in enumerate(str1):
		for (j, char2) in enumerate(str2):
			if char1 == char2:
				diff[i + 1][j + 1] = diff[i][j] + 1
			else:
				diff[i + 1][j + 1] = max(diff[i + 1][j], diff[i][j + 1])
	return diff[length][length]
print(lcs(input(), input()))


def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	print(curr_lcs[-1])
s1 = input()
s2 = input()
lcs_len(s1, s2)


s1 = input().strip()
s2 = input().strip()
n = len(s1)
assert n == len(s2)
currow = [0] * (n + 1)
for i in range(n):
	s1i = s1[i]
	prevrow = currow
	currow = [0]
	cr = 0
	for (s2j, nr, nr1) in zip(s2, prevrow, prevrow[1:]):
		if s1i == s2j:
			cr = 1 + nr
		elif cr < nr1:
			cr = nr1
		currow.append(cr)
print(currow[-1])


def longest_common_child_length(arr1, arr2):
	n1 = len(arr1)
	n2 = len(arr2)
	cache = [0] * n1
	for i2 in range(0, n2):
		prev = 0
		for i1 in range(0, n1):
			if arr1[i1] == arr2[i2]:
				longest = prev + 1
			elif i1 == 0:
				longest = cache[i1]
			else:
				longest = max(cache[i1 - 1], cache[i1])
			prev = cache[i1]
			cache[i1] = longest
	return cache[n1 - 1]

def encode(string):
	return [ord(c) - ord('A') for c in iter(string)]
str1 = encode(input().strip())
str2 = encode(input().strip())
print(longest_common_child_length(str1, str2))


def check(s1, s2, n1, n2):
	last = [0] * n1
	for i in range(n2):
		c2 = s2[i]
		this = last.copy()
		for j in range(n1):
			c1 = s1[j]
			if c1 == c2:
				if j == 0:
					this[j] = 1
				else:
					this[j] = max(last[j - 1] + 1, this[j - 1])
			elif j >= 1:
				this[j] = max(this[j - 1], this[j])
		last = this
	return last[-1]
s1 = input().strip()
s2 = input().strip()
n1 = len(s1)
n2 = len(s2)
print(check(s1, s2, n1, n2))


def lcs(a, b):
	lengths = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				lengths[i + 1][j + 1] = lengths[i][j] + 1
			else:
				lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
	return lengths[-1][-1]

def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]

def main():
	s1 = input()
	s2 = input()
	print(lcs_len(s1, s2))
main()


def solve(s1, s2):
	n = len(s1)
	dp = [0] * (n + 1)
	for i in range(n):
		p = None
		dpp = dp.copy()
		for j in range(n):
			if s2[j] == s1[i]:
				p = j
			if p != None:
				v1 = dpp[j]
				v2 = 1 + dpp[p - 1]
				if v2 > v1:
					dp[j] = v2
	print(dp[n - 1])
solve(input(), input())


def solve(a, b):
	n = len(a)
	m = len(b)
	memos = [0 for i in range(n + 1)]
	for j in range(m - 1, -1, -1):
		memos_plus1 = memos
		memos = [None for i in range(n + 1)]
		memos[n] = 0
		for i in range(n - 1, -1, -1):
			if a[i] == b[j]:
				memos[i] = memos_plus1[i + 1] + 1
			else:
				memos[i] = max(memos[i + 1], memos_plus1[i])
	return memos[0]
a = input().strip()
b = input().strip()
print(solve(a, b))


def lcs(a, b):
	s1 = [0 for x in range(len(a) + 1)]
	s2 = s1[:]
	l = [x for x in range(1, len(a) + 1)]
	for i in l:
		for j in l:
			if a[i - 1] == b[j - 1]:
				s2[j] = s1[j - 1] + 1
			else:
				s2[j] = s1[j] if s1[j] >= s2[j - 1] else s2[j - 1]
		s1 = s2[:]
	print(s2[len(a)])
a = input()
b = input()
lcs(a, b)


import sys
a = input().strip()
b = input().strip()
n = len(a)

def LCS(a, b):
	n = len(a)
	line = [0] * (n + 1)
	pl = line.copy()
	for ai in range(1, n + 1):
		char_a = a[ai - 1]
		nl = line.copy()
		for bi in range(1, n + 1):
			if char_a == b[bi - 1]:
				nl[bi] = pl[bi - 1] + 1
			else:
				nl[bi] = max(pl[bi], nl[bi - 1])
		pl = nl.copy()
	return nl[n]
print(LCS(a, b))


def child_length():
	s1 = input()
	s2 = input()
	l1 = len(s1)
	l2 = len(s2)
	max_len = max(l1, l2)
	tracker = [[0] * (max_len + 1) for i in range(max_len + 1)]
	for i in range(0, l1):
		for j in range(0, l2):
			if s1[i] == s2[j]:
				tracker[i + 1][j + 1] = tracker[i][j] + 1
			else:
				a = tracker[i + 1][j]
				b = tracker[i][j + 1]
				if a > b:
					tracker[i + 1][j + 1] = a
				else:
					tracker[i + 1][j + 1] = b
	print(tracker[l1][l2])
child_length()


A = input()
B = input()

def solve(A, B):
	if len(A) > len(B):
		(A, B) = (B, A)
	prev = [0] * (len(A) + 1)
	cur = [0] * (len(A) + 1)
	for b in B:
		(prev, cur) = (cur, prev)
		for (i, a) in enumerate(A):
			if a == b:
				cur[i + 1] = prev[i] + 1
			else:
				cur[i + 1] = max(cur[i], prev[i + 1])
	return cur[-1]
print(solve(A, B))


def longest(a, b):
	last_longest = [0] * (1 + len(b))
	next_longest = [0] * (1 + len(b))
	for i in range(len(a)):
		for j in range(len(b)):
			if a[i] == b[j]:
				next_longest[j + 1] = 1 + last_longest[j]
			else:
				next_longest[j + 1] = max(next_longest[j], last_longest[j + 1])
		(last_longest, next_longest) = (next_longest, last_longest)
	return max(last_longest)
print(longest(input(), input()))


from array import array

def lcsLength(str1, str2):
	m = len(str1)
	n = len(str2)
	prevRow = array('i', [0 for i in range(n + 1)])
	curRow = array('i', [0 for i in range(n + 1)])
	for i in range(m):
		ch = str1[i]
		for j in range(n):
			if ch == str2[j]:
				curRow[j + 1] = prevRow[j] + 1
			else:
				curRow[j + 1] = max(curRow[j], prevRow[j + 1])
		tmp = prevRow
		prevRow = curRow
		curRow = tmp
	return prevRow[n]
str1 = input().strip()
str2 = input().strip()
print(lcsLength(str1, str2))


def comu(s1, s2):
	lon = len(s1)
	zeros = [0] * (lon + 2)
	millors = [zeros.copy() for i in range(3)]
	for f in range(lon - 1, -1, -1):
		for c in range(lon - 1, -1, -1):
			if s1[f] == s2[c]:
				millors[0][c] = 1 + millors[1][c + 1]
			else:
				millors[0][c] = max(millors[0][c + 1], millors[1][c])
		millors.pop(2)
		millors = [zeros.copy(), millors[0], millors[1]]
	millor = millors[1][0]
	return millor
import sys
s1 = sys.stdin.readline().strip()
s2 = sys.stdin.readline().strip()
print(comu(s1, s2))


def solve(a, b):
	row_1 = [0 for _ in range(len(b) + 1)]
	row_2 = [0 for _ in range(len(b) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				row_2[j + 1] = row_1[j] + 1
			else:
				row_2[j + 1] = max(row_1[j + 1], row_2[j])
		row_1 = row_2
		row_2 = [0 for _ in range(len(b) + 1)]
	return row_1[len(b)]
a = input()
b = input()
print(solve(a, b))


def solve(a, b):
	n = len(a)
	cnt1 = [0] * (n + 1)
	cnt2 = [0] * (n + 1)
	for i in range(n):
		for j in range(n):
			if a[i] == b[j]:
				r = cnt1[j] + 1
			else:
				r = max(cnt2[j], cnt1[j + 1])
			cnt2[j + 1] = r
		(cnt1, cnt2) = (cnt2, cnt1)
	return cnt1[n]
a = input().strip()
b = input().strip()
print(solve(a, b))


def lcs(a, b):
	prev_ai = [0 for i in range(len(a) + 1)]
	for ai in range(len(a)):
		new_ai = [0]
		for bi in range(len(b)):
			if a[ai] == b[bi]:
				new_ai.append(prev_ai[bi] + 1)
			else:
				new_ai.append(max(new_ai[-1], prev_ai[bi + 1]))
		prev_ai = new_ai
	return new_ai[len(a)]
a = input()
b = input()
print(lcs(a, b))


def buildLCS():
	s1 = input()
	s2 = input()
	N = len(s2) + 1
	start = 1
	s1_end = len(s1) - 1
	s2_end = len(s2) - 1
	while start <= s1_end and start <= s2_end and (s1[start] == s2[start]):
		start += 1
	LCSrow1 = [0] * N
	LCS = [0] * N
	dict()
	longest = 0
	startcol = 1
	for row in range(start - 1, len(s1)):
		s1_end = len(s1) - 1
		s2_end = len(s2) - 1
		while row <= s1_end and startcol <= s2_end and (s1[row] == s2[startcol]):
			startcol += 1
		for col in range(startcol - 1, len(s2)):
			if s2[col] != s1[row]:
				if LCS[col] >= LCSrow1[col + 1]:
					LCS[col + 1] = LCS[col]
				else:
					LCS[col + 1] = LCSrow1[col + 1]
			elif s2[col] == s1[row]:
				LCS[col + 1] = LCSrow1[col] + 1
			else:
				LCS[col + 1] = 0
			if LCS[col + 1] > longest:
				longest = LCS[col + 1]
		LCSrow1 = list(LCS)
	return longest
print(buildLCS())


import sys

def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]

def main():
	f = sys.stdin
	s1 = f.readline().strip()
	s2 = f.readline().strip()
	print(lcs_len(s1, s2))
main()


def lcs_length(a, b):
	(n, m) = (len(a), len(b))
	(previous, current) = ([0] * (m + 1), [0] * (m + 1))
	for i in range(n):
		(previous, current) = (current, previous)
		for j in range(m):
			if a[i] == b[j]:
				current[j] = previous[j - 1] + 1
			else:
				current[j] = max(previous[j], current[j - 1])
	return current[m - 1]
a = input().strip()
b = input().strip()
print(lcs_length(a, b))


def check(a, b):
	prev = [0 for x in range(len(s1) + 1)]
	value = 0
	for i in range(len(a)):
		curr = [0]
		for j in range(len(b)):
			if b[i] == a[j]:
				value = 1 + prev[j]
			else:
				value = max(prev[j + 1], curr[j])
			curr.append(value)
		prev = curr
	return prev[len(b)]
s1 = input().strip()
s2 = input().strip()
print(check(s1, s2))


def solve(s1, s2):
	N1 = len(s1)
	arr1 = [0] * (N1 + 1)
	arr2 = [0] * (N1 + 1)
	for c2 in s2:
		for (i, c1) in enumerate(s1):
			if c1 == c2:
				arr2[i + 1] = 1 + arr1[i]
			else:
				arr2[i + 1] = max(arr2[i], arr1[i + 1])
		(arr2, arr1) = (arr1, arr2)
	return arr1[-1]
print(solve(input(), input()))


s1 = input().strip()
s2 = input().strip()

def lcm(s1, s2):
	prev_row = [0 for letter in range(len(s2) + 1)]
	current_row = [0 for letter in range(len(s2) + 1)]
	for (index1, letter1) in enumerate(s1):
		prev_row = current_row
		current_row = [0 for letter in range(len(s2) + 1)]
		for (index2, letter2) in enumerate(s2):
			if letter1 == letter2:
				current_row[index2 + 1] = prev_row[index2] + 1
			else:
				current_row[index2 + 1] = max(current_row[index2], prev_row[index2 + 1])
	return current_row[-1]
print(lcm(s1, s2))


a = input()
b = input()

def func(a, b):
	f = [0] * (len(a) + 1)
	for i in range(1, len(a) + 1):
		g = [0] * (len(a) + 1)
		for j in range(1, len(b) + 1):
			if a[i - 1] == b[j - 1]:
				g[j] = f[j - 1] + 1
			else:
				g[j] = f[j] if f[j] > g[j - 1] else g[j - 1]
		f = g
	return f[-1]
print(func(a, b))


def lcs():
	A = input()
	B = input()
	n = len(B)
	m = len(A)
	vect1 = [0 for i in range(5001)]
	vect2 = [0 for i in range(5001)]
	temp = []
	for i in range(m):
		for j in range(n):
			if A[i] == B[j]:
				vect2[j + 1] = vect1[j] + 1
			else:
				vect2[j + 1] = max(vect1[j + 1], vect2[j])
		temp = vect2
		vect2 = vect1
		vect1 = temp
	print(vect1[n])
lcs()


def LCS(A, B):
	(a_size, b_size) = (len(A), len(B))
	new = [0] * (b_size + 1)
	old = [0] * (b_size + 1)
	for a in A:
		(old, new) = (new, old)
		for (i, b) in enumerate(B, 1):
			if a == b:
				new[i] = 1 + old[i - 1]
			else:
				new[i] = max(new[i - 1], old[i])
	return new[-1]
print(LCS(input(), input()))


import sys

def main(str1, str2):
	prevArr = [0] * (len(str1) + 1)
	curArr = [0] * (len(str1) + 1)
	for (i, c1) in enumerate(str1):
		for (j, c2) in enumerate(str2):
			if c1 == c2:
				curArr[j] = prevArr[j - 1] + 1
			elif prevArr[j] > curArr[j - 1]:
				curArr[j] = prevArr[j]
			else:
				curArr[j] = curArr[j - 1]
		(curArr, prevArr) = (prevArr, curArr)
	print(prevArr[-2])
str1 = input()
str2 = input()
main(str1, str2)


def main():
	str1 = input().strip()
	str2 = input().strip()
	table = [0 for i in range(len(str1) + 1)]
	for i in range(1, len(str2) + 1):
		next_table = [0 for i in range(len(str1) + 1)]
		for j in range(1, len(str1) + 1):
			if str1[j - 1] == str2[i - 1]:
				next_table[j] = table[j - 1] + 1
			elif table[j] > next_table[j - 1]:
				next_table[j] = table[j]
			else:
				next_table[j] = next_table[j - 1]
		table = next_table
	print(table[len(str1)])
main()


import collections
import functools
str1 = input()
str2 = input()

def lcs(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
print(lcs(str1, str2))


first_string = input().strip()
second_string = input().strip()

def largest_common_substring(first_string, second_string):
	curr_memoized_row = [0 for _ in range(len(second_string) + 1)]
	for row in range(1, len(first_string) + 1):
		prev_memoized_row = curr_memoized_row
		curr_memoized_row = [0 for _ in range(len(second_string) + 1)]
		for col in range(1, len(second_string) + 1):
			if first_string[row - 1] == second_string[col - 1]:
				curr_memoized_row[col] = prev_memoized_row[col - 1] + 1
			elif curr_memoized_row[col - 1] > prev_memoized_row[col]:
				curr_memoized_row[col] = curr_memoized_row[col - 1]
			else:
				curr_memoized_row[col] = prev_memoized_row[col]
	return curr_memoized_row[len(second_string)]
print(largest_common_substring(first_string, second_string))


def get_index_dictionary(s):
	result = dict()
	for i in range(len(s)):
		letter = s[i]
		if letter not in result:
			result[letter] = [i]
		else:
			result[letter].append(i)
	return result
s = input().strip()
t = input().strip()
n = max(len(s), len(t))
inf = n + 1
min_length = [-1] + [inf] * n

def process(index_arr):
	new_value = dict()
	m = len(index_arr)
	i = 0
	j = 0
	while j < m and i < n + 1:
		if min_length[i] >= index_arr[j]:
			j += 1
		else:
			assert min_length[i] < index_arr[j]
			if min_length[i + 1] < index_arr[j]:
				i += 1
			else:
				new_value[i + 1] = index_arr[j]
				i += 1
				j += 1
	for k in new_value:
		min_length[k] = new_value[k]
index_t = get_index_dictionary(t)
for k in range(len(s)):
	index_arr = index_t.get(s[k], [])
	process(index_arr)
for i in range(n, -1, -1):
	if min_length[i] < inf:
		print(i)
		break


a = input().strip()
b = input().strip()

def best(a, b):
	path = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
	for i in range(len(a)):
		p = path[i]
		pp = path[i + 1]
		prev = 0
		for j in range(len(b)):
			if a[i] == b[j]:
				prev = pp[j + 1] = p[j] + 1
			else:
				prev = pp[j + 1] = max(p[j + 1], prev)
	return path[len(a)][len(b)]
print(best(a, b))


h = {}

def subseq_work(s1, s2):
	m = len(s1)
	n = len(s2)
	prev_row = [0 for i in range(n + 1)]
	for i in range(1, m + 1):
		current_row = {0: 0}
		for j in range(1, n + 1):
			current_row[j] = current_row
			if s1[i - 1] == s2[j - 1]:
				current_row[j] = 1 + prev_row[j - 1]
			elif current_row[j - 1] > prev_row[j]:
				current_row[j] = current_row[j - 1]
			else:
				current_row[j] = prev_row[j]
		prev_row = current_row
	return current_row[n]

def subseq1(s1, s2):
	m = len(s1)
	n = len(s2)
	prev_row = [0 for i in range(n + 1)]
	prev_indices = []
	for i in range(1, m + 1):
		current_row = {0: 0}
		char = s1[i - 1]
		if char in s2h:
			curr_indices = s2h[char]
		else:
			curr_indices = []
		j = 0
		k = 0
		new_indices = [x for x in prev_indices]
		if len(new_indices) == 0 and len(curr_indices) > 0:
			new_indices.append(curr_indices[0])
		else:
			while j < len(curr_indices):
				if k < len(prev_indices):
					if curr_indices[j] <= prev_indices[k]:
						new_indices[k] = curr_indices[j]
						j += 1
						while j < len(curr_indices) and curr_indices[j] <= prev_indices[k]:
							j += 1
					k += 1
				else:
					if curr_indices[j] > prev_indices[-1]:
						new_indices.append(curr_indices[j])
						break
					j += 1
		prev_indices = new_indices
	return len(new_indices)
s1 = input().strip()
s2 = input().strip()
s2h = {}
for (i, char) in enumerate(s2):
	if char in s2h:
		s2h[char].append(i)
	else:
		s2h[char] = [i]
print(subseq1(s1, s2))


import time
import random

def fc(a, b):
	if a[0] == b[0]:
		return fc(a[1:], b[1:]) + 1
	if a[-1] == b[-1]:
		return fc(a[:-1], b[:-1]) + 1
	c = []
	(la, lb) = (len(a) + 1, len(b) + 1)
	last_row = [0] * lb
	if debug == 1:
		global s
		print('array init: ' + str(time.time() - s))
		s = time.time()
	for i in range(1, la, 1):
		current_row = [0] * lb
		for j in range(1, lb, 1):
			if a[i - 1] == b[j - 1]:
				current_row[j] = last_row[j - 1] + 1
			elif current_row[j - 1] > last_row[j]:
				current_row[j] = current_row[j - 1]
			else:
				current_row[j] = last_row[j]
		last_row = current_row
	return last_row[lb - 1]
debug = 0
if debug == 1:
	s = time.time()
	(a, b, n) = ('A', 'Z', 5000)
	for _ in range(n):
		a += chr(random.randint(65, 90))
		b += chr(random.randint(65, 90))
	a += 'Z'
	b += 'A'
	print('input generation: ' + str(time.time() - s))
	s = time.time()
	print(fc(a, b))
	print('loop processing: ' + str(time.time() - s))
else:
	(a, b) = (input().strip(), input().strip())
	print(fc(a, b))


import sys

def lcs_length(a, b):
	table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
	for (i, ca) in enumerate(a, 1):
		for (j, cb) in enumerate(b, 1):
			table[i][j] = table[i - 1][j - 1] + 1 if ca == cb else max(table[i][j - 1], table[i - 1][j])
	return table[-1][-1]
stra = input().strip()
strb = input().strip()
print(lcs_length(stra, strb))


def lcs(a, b):
	a_n = len(a)
	b_n = len(b)
	(prev, curr) = ([0] * (b_n + 1) for _ in range(2))
	for i in range(1, a_n + 1):
		(curr, prev) = (prev, curr)
		for j in range(1, b_n + 1):
			if a[i - 1] == b[j - 1]:
				curr[j] = 1 + prev[j - 1]
			else:
				p = prev[j]
				c = curr[j - 1]
				curr[j] = p if p > c else c
	return curr[len(b)]
s_1 = input().strip()
s_2 = input().strip()
print(lcs(s_1, s_2))


def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
s1 = input()
s2 = input()
print(lcs_len(s1, s2))


def commonChild():
	s0 = input().strip()
	s1 = input().strip()
	if len(s0) > len(s1):
		(s0, s1) = (s1, s0)
	a = [0] * (len(s0) + 1)
	for r in range(1, 1 + len(s1)):
		leftUp = 0
		for c in range(1, 1 + len(s0)):
			up = a[c]
			if s0[c - 1] == s1[r - 1]:
				a[c] = leftUp + 1
			elif a[c - 1] > a[c]:
				a[c] = a[c - 1]
			leftUp = up
	print(a[-1])
commonChild()


def xchild(a, b):
	(k, m) = (len(a), len(b) + 1)
	n = [0] * m
	for i in range(k):
		prev = n[1]
		for j in range(1, m):
			if a[i] == b[j - 1]:
				(n[j], prev) = (prev + 1, n[j])
			else:
				prev = n[j]
				n[j] = n[j - 1] if n[j - 1] > n[j] else n[j]
	return n[m - 1]
print(xchild(input().strip(), input().strip()))


import sys

def cc(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
s1 = input().strip()
s2 = input().strip()
print(cc(s1, s2))


def get_longest_child(s, t):
	dp = [0] * (len(t) + 1)
	for i in range(1, len(s) + 1):
		new_dp = [0]
		for j in range(1, len(dp)):
			if s[i - 1] == t[j - 1]:
				new_dp.append(dp[j - 1] + 1)
			else:
				new_dp.append(new_dp[-1] if new_dp[-1] > dp[j] else dp[j])
		dp = new_dp
	return dp[-1]
print(get_longest_child(input(), input()))


def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
string1 = input()
string2 = input()
len_string1 = len(string1)
len_string2 = len(string2)
print(lcs_len(string1, string2))


def read_data():
	str1 = input().strip()
	str2 = input().strip()
	return (str1, str2)

def max(x, y):
	if x > y:
		return x
	return y

def solve(str1, str2):
	last_subproblems = [0] * (len(str2) + 1)
	for i in range(0, len(str1)):
		subproblems = [0]
		for j in range(0, len(str2)):
			s = max(last_subproblems[j + 1], subproblems[j])
			if str1[i] == str2[j]:
				s = max(s, 1 + last_subproblems[j])
			subproblems.append(s)
		last_subproblems = subproblems
	return subproblems[len(str2)]
(str1, str2) = read_data()
print(solve(str1, str2))


import sys

def commonChild(x, y):
	ll = max(len(x), len(y))
	curr = [0] * (ll + 1)
	prev = [0] * (ll + 1)
	for i in range(len(x)):
		for j in range(len(y)):
			if x[i] == y[j]:
				curr[j + 1] = prev[j] + 1
			else:
				curr[j + 1] = curr[j] if curr[j] > prev[j + 1] else prev[j + 1]
		(curr, prev) = (prev, curr)
	return prev[-1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


def longest_substring(s1, s2):
	dp = [0] * (len(s2) + 1)
	for char1 in s1:
		prev = 0
		for (i, char2) in enumerate(s2, start=1):
			temp = dp[i]
			if char1 == char2:
				dp[i] = prev + 1
			else:
				dp[i] = max(dp[i], dp[i - 1])
			prev = temp
	return dp[-1]
s1 = input()
s2 = input()
print(longest_substring(s1, s2))


import sys

def LCS(a, b):
	n = len(a)
	m = len(b)
	lis1 = [0 for _ in range(m + 1)]
	lis2 = [0 for _ in range(m + 1)]
	for i in range(n):
		letter = a[i]
		if i % 2:
			for j in range(1, m + 1):
				if b[j - 1] == letter:
					lis2[j] = lis1[j - 1] + 1
				elif lis2[j - 1] >= lis1[j]:
					lis2[j] = lis2[j - 1]
				else:
					lis2[j] = lis1[j]
		else:
			for j in range(1, m + 1):
				if b[j - 1] == letter:
					lis1[j] = lis2[j - 1] + 1
				elif lis1[j - 1] >= lis2[j]:
					lis1[j] = lis1[j - 1]
				else:
					lis1[j] = lis2[j]
	return max(lis1[-1], lis2[-1])
s1 = input().strip()
s2 = input().strip()
print(LCS(s1, s2))


import sys

def longest_common(s1, s2):
	first_line = list([0] * (len(s1) + 1))
	second_line = first_line.copy()
	for j in range(len(s1)):
		for i in range(len(s2)):
			if s1[j] == s2[i]:
				second_line[i + 1] = first_line[i] + 1
			elif first_line[i + 1] > second_line[i]:
				second_line[i + 1] = first_line[i + 1]
			else:
				second_line[i + 1] = second_line[i]
		first_line = second_line
		second_line = list([0] * (len(s1) + 1))
	return first_line[-1]
s1 = input().strip()
s2 = input().strip()
if len(s1) == 0 or len(s2) == 0:
	print(0)
else:
	print(longest_common(s1, s2))


import sys

def commonChild(s1, s2):
	prevrow = [0 for i in range(len(s1) + 1)]
	for char2 in s2:
		row = [0]
		for (j, char1) in enumerate(s1):
			if char1 == char2:
				row.append(prevrow[j] + 1)
			else:
				row.append(max(row[j], prevrow[j + 1]))
		prevrow = row
	return row[-1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def commonChild(s1, s2):
	last = [0] * (len(s1) + 1)
	cur = [0] * (len(s1) + 1)
	for a in s2:
		for (i, b) in enumerate(s1, 1):
			cur[i] = max(last[i], cur[i - 1], 0 if a != b else last[i - 1] + 1)
		(last, cur) = (cur, last)
	return last[-1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def getcorresponding(s1, s2, node, depth, target):
	i = depth + 1
	j = node.corresponding + 1
	l = s1[i]
	while j < target:
		if s2[j] == l:
			return j
		j += 1
	return False

class MyNode:

	def __init__(self, prev=None, corresponding=None):
		if prev == None:
			self.corresponding = -1
			self.size = 0
		else:
			self.size = prev.size + 1
			self.corresponding = corresponding

def commonChild(s1, s2):
	nodes = [MyNode()]
	bestsize = 0
	depth = -1
	bestcorresponding = [-1]
	while depth < len(s1) - 1:
		newnodes = []
		oldbests = bestcorresponding[:]
		for node in nodes:
			if node.corresponding <= oldbests[node.size]:
				newnodes.append(node)
				if node.size + 1 == len(bestcorresponding):
					c = getcorresponding(s1, s2, node, depth, len(s2))
					if c is not False:
						N = MyNode(node, c)
						newnodes.append(N)
						if N.size > bestsize:
							bestsize = N.size
						bestcorresponding.append(c)
				else:
					c = getcorresponding(s1, s2, node, depth, bestcorresponding[node.size + 1])
					if c is not False:
						N = MyNode(node, c)
						newnodes.append(N)
						if N.size > bestsize:
							bestsize = N.size
						bestcorresponding[node.size + 1] = c
		depth += 1
		nodes = newnodes
	return bestsize
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def commonChild(s1, s2):
	prev_lcs = [0] * (len(s1) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def commonChild(s1, s2):
	n = len(s1)
	(this, prev) = ([0] * (n + 1), None)
	for i in range(1, n + 1):
		(this, prev) = ([0] * (n + 1), this)
		for j in range(1, n + 1):
			if s1[i - 1] == s2[j - 1]:
				this[j] = prev[j - 1] + 1
			elif this[j - 1] >= prev[j]:
				this[j] = this[j - 1]
			else:
				this[j] = prev[j]
	return this[n]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def commonChild(s1, s2, n):
	prev_lcs = [0] * (n + 1)
	curr_lcs = [0] * (n + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (i, c2) in enumerate(s2, 1):
			curr_lcs[i] = 1 + prev_lcs[i - 1] if c1 == c2 else max(prev_lcs[i], curr_lcs[i - 1])
	return curr_lcs[-1]
s1 = input().strip()
s2 = input().strip()
n = len(s1)
result = commonChild(s1, s2, n)
print(result)


import sys

def commonChild(s1, s2):
	(len_s1, len_s2) = (len(s1), len(s2))
	(dp_prev, dp_curr) = ([0] * (len_s1 + 1), [0] * (len_s1 + 1))
	for x2 in range(len_s2):
		curr_char = s2[x2]
		for x1 in range(len_s1):
			if curr_char == s1[x1]:
				dp_curr[x1 + 1] = dp_prev[x1] + 1
			else:
				dp_curr[x1 + 1] = max(dp_curr[x1], dp_prev[x1 + 1])
		dp_prev = dp_curr[:]
	return dp_curr[len_s1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def solvethisbitch():
	s1 = input().strip()
	s2 = input().strip()
	x = len(s1) + 1
	x = int(x)
	a = [0] * x
	c = [0] * x
	for sa in s1:
		for (g, sb) in enumerate(s2, 1):
			a[g] = 1 + c[g - 1] if sa == sb else max(c[g], a[g - 1])
		c = list(a)
	print(c[x - 1])
solvethisbitch()


import sys

def commonChild(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def commonChild(s1, s2):
	ln = len(s2) + 1
	(prev, cur) = ([0] * ln, [0] * ln)
	for (i, c1) in enumerate(s1):
		(cur, prev) = (prev, cur)
		cur[0] = 0
		for (j, c2) in enumerate(s2):
			if c1 == c2:
				cur[j + 1] = prev[j] + 1
			else:
				cur[j + 1] = max(cur[j], prev[j + 1])
	return cur[-1]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


import sys

def commonChild(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
s1 = input()
s2 = input()
result = commonChild(s1, s2)
print(result)


import sys

def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
s1 = input().strip()
s2 = input().strip()
print(lcs_len(s1, s2))


import sys

def lcs_len(s1, s2):
	prev_lcs = [0] * (len(s2) + 1)
	curr_lcs = [0] * (len(s2) + 1)
	for c1 in s1:
		(curr_lcs, prev_lcs) = (prev_lcs, curr_lcs)
		for (j, c2) in enumerate(s2, 1):
			curr_lcs[j] = 1 + prev_lcs[j - 1] if c1 == c2 else max(prev_lcs[j], curr_lcs[j - 1])
	return curr_lcs[-1]
x = input()
y = input()
res = lcs_len(x, y)
print(res)


import sys

def commonChild(s1, s2):
	d = [0 for i in range(len(s2) + 1)]
	x = 0
	for i in range(len(s1)):
		for j in range(len(s2)):
			old = d[j + 1]
			if s1[i] == s2[j]:
				d[j + 1] = x + 1
			elif d[j] > d[j + 1]:
				d[j + 1] = d[j]
			x = old
		x = 0
	return d[len(s2)]
s1 = input().strip()
s2 = input().strip()
result = commonChild(s1, s2)
print(result)


def common_child(s1, s2):
	res = [0] * (len(s2) + 1)
	for i in range(len(s1)):
		(a0, a1) = (0, res[1])
		for j in range(len(s2)):
			(a0, a1) = (a1, res[j + 1])
			if s1[i] == s2[j]:
				res[j + 1] = a0 + 1
			else:
				res[j + 1] = a1 if a1 > res[j] else res[j]
	return res[-1]
a = input().strip()
b = input().strip()
print(common_child(a, b))