Given two strings, $a$ and $\boldsymbol{b}$, find and print the total number of ways to insert a character at any position in string $\class{ML__boldsymbol}{\boldsymbol{a}}$ such that the length of the Longest Common Subsequence of characters in the two strings increases by one.

Input Format

The first line contains a single string denoting $\class{ML__boldsymbol}{\boldsymbol{a}}$. 

The second line contains a single string denoting $\boldsymbol{b}$.

Constraints

Scoring     

$1\leq|a|,|b|\leq5000$
Strings $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).
The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).

Subtask     

$1\le|a|,|b|\le1000$ for $\boldsymbol{66.67\%}$ of the maximum score.  

Output Format

Print a single integer denoting the total number of ways to insert a character into string $\class{ML__boldsymbol}{\boldsymbol{a}}$ in such a way that the length of the longest common subsequence of $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ increases by one.

Sample Input
aa
baaa

Sample Output
4

Explanation

The longest common subsequence shared by $a=\text{"a}\textbf{a}$ and $b=\text{"baaa''}$ is aa, which has a length of $2$. There are two ways that the length of the longest common subsequence can be increased to $3$ by adding a single character to $\class{ML__boldsymbol}{\boldsymbol{a}}$:

There are $3$ different positions in string $\class{ML__boldsymbol}{\boldsymbol{a}}$ where we could insert an additional a to create longest common subsequence aaa (i.e., at the beginning, middle, and end of the string). 
We can insert a b at the beginning of the string for a new longest common subsequence of baa.

As we have $3+1=4$ ways to insert an alphanumeric character into $\class{ML__boldsymbol}{\boldsymbol{a}}$ and increase the length of the longest common subsequence by one, we print $\begin{array}{c}4\end{array}$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


def getCount(s1, s2):
	l1 = len(s1)
	l2 = len(s2)
	dp1 = [[0 for i in range(l2 + 1)] for j in range(l1 + 1)]
	for i in range(1, l1 + 1):
		for j in range(1, l2 + 1):
			if s1[i - 1] == s2[j - 1]:
				dp1[i][j] = dp1[i - 1][j - 1] + 1
			else:
				dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1])
	lcs = dp1[l1][l2] + 1
	s11 = s1[::-1]
	s22 = s2[::-1]
	l1 = len(s11)
	l2 = len(s22)
	dp2 = [[0 for i in range(l2 + 1)] for i in range(l1 + 1)]
	for i in range(1, l1 + 1):
		for j in range(1, l2 + 1):
			if s11[i - 1] == s22[j - 1]:
				dp2[i][j] = dp2[i - 1][j - 1] + 1
			else:
				dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - 1])
	ans = 0
	sets = set()
	for i in range(len(s2)):
		sets.add(s2[i])
	list1 = list(sets)
	list2 = [[] for j in range(1000)]
	findAlloccurances(s2, list2)
	for i in range(l1 + 1):
		for j in range(len(list1)):
			for k in range(len(list2[ord(list1[j])])):
				x = list2[ord(list1[j])][k]
				if dp1[i][x] + 1 + dp2[l1 - i][l2 - x - 1] == lcs:
					ans += 1
					break
	return ans

def findAlloccurances(s2, list2):
	length = len(s2)
	for i in range(length):
		list2[ord(s2[i])].append(i)
s1 = input()
s2 = input()
count = getCount(s1, s2)
print(count)


def getCount(s1, s2):
	l1 = len(s1)
	l2 = len(s2)
	dp1 = [[0 for i in range(l2 + 1)] for j in range(l1 + 1)]
	for i in range(1, l1 + 1):
		for j in range(1, l2 + 1):
			if s1[i - 1] == s2[j - 1]:
				dp1[i][j] = dp1[i - 1][j - 1] + 1
			else:
				dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1])
	lcs = dp1[l1][l2] + 1
	s11 = s1[::-1]
	s22 = s2[::-1]
	l1 = len(s11)
	l2 = len(s22)
	dp2 = [[0 for i in range(l2 + 1)] for i in range(l1 + 1)]
	for i in range(1, l1 + 1):
		for j in range(1, l2 + 1):
			if s11[i - 1] == s22[j - 1]:
				dp2[i][j] = dp2[i - 1][j - 1] + 1
			else:
				dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - 1])
	ans = 0
	sets = set()
	for i in range(len(s2)):
		sets.add(s2[i])
	list1 = list(sets)
	list2 = [[] for j in range(1000)]
	findAlloccurances(s2, list2)
	for i in range(l1 + 1):
		for j in range(len(list1)):
			for k in range(len(list2[ord(list1[j])])):
				x = list2[ord(list1[j])][k]
				if dp1[i][x] + 1 + dp2[l1 - i][l2 - x - 1] == lcs:
					ans += 1
					break
	return ans

def findAlloccurances(s2, list2):
	length = len(s2)
	for i in range(length):
		list2[ord(s2[i])].append(i)
s1 = input()
s2 = input()
count = getCount(s1, s2)
print(count)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


MAX = 256

def numberofways(A, B, N, M):
	pos = [[] for _ in range(MAX)]
	for i in range(M):
		pos[ord(B[i])].append(i + 1)
	dpl = [[0] * (M + 2) for _ in range(N + 2)]
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if A[i - 1] == B[j - 1]:
				dpl[i][j] = dpl[i - 1][j - 1] + 1
			else:
				dpl[i][j] = max(dpl[i - 1][j], dpl[i][j - 1])
	LCS = dpl[N][M]
	dpr = [[0] * (M + 2) for _ in range(N + 2)]
	for i in range(N, 0, -1):
		for j in range(M, 0, -1):
			if A[i - 1] == B[j - 1]:
				dpr[i][j] = dpr[i + 1][j + 1] + 1
			else:
				dpr[i][j] = max(dpr[i + 1][j], dpr[i][j + 1])
	ans = 0
	for i in range(N + 1):
		for j in range(MAX):
			for x in pos[j]:
				if dpl[i][x - 1] + dpr[i + 1][x + 1] == LCS:
					ans += 1
					break
	return ans
A = input()
B = input()
N = len(A)
M = len(B)
print(numberofways(A, B, N, M))


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


def LCS(a, b):
	(na, nb) = (len(a), len(b))
	dp = [[0 for _ in range(nb)] for _ in range(na)]
	for i in range(na):
		for j in range(nb):
			if a[i] == b[j]:
				dp[i][j] = (dp[i - 1][j - 1] if i >= 1 and j >= 1 else 0) + 1
			else:
				dp[i][j] = max(dp[i - 1][j] if i >= 1 else 0, dp[i][j - 1] if j >= 1 else 0)
	return dp

def tutzkiAndLcs(a, b):
	(na, nb) = (len(a), len(b))
	dp1 = LCS(a, b)
	dp2 = LCS(a[::-1], b[::-1])
	prev = dp1[-1][-1]
	res = set()
	for i in range(0, len(a) + 1):
		for j in range(len(b)):
			if (i, b[j]) in res:
				continue
			t = 0
			if i != 0 and j != 0:
				t += dp1[i - 1][j - 1]
			if i != na and j != nb - 1:
				t += dp2[na - 1 - i][nb - 1 - j - 1]
			if t == prev:
				res.add((i, b[j]))
	return len(res)
a = input()
b = input()
result = tutzkiAndLcs(a, b)
print(result)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def retyrn(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = retyrn(s1, s2)
dpr = retyrn(s1[::-1], s2[::-1])
retyrn = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == retyrn:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import math
import os
import random
import re
import sys
import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


import string

def lcs(s1, s2):
	n = len(s1)
	m = len(s2)
	dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if s1[i] == s2[j]:
				dp[i + 1][j + 1] = dp[i][j] + 1
			else:
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	return dp

def alpIndexes(s, alp):
	d = dict()
	for letter in alp:
		d[letter] = []
	for i in range(len(s)):
		d[s[i]].append(i)
	return d
s1 = input().strip()
s2 = input().strip()
n = len(s1)
m = len(s2)
chars = list(string.ascii_lowercase)
charIndexes = alpIndexes(s2, chars)
dpl = lcs(s1, s2)
dpr = lcs(s1[::-1], s2[::-1])
lcs = dpl[n][m]
ans = 0
for i in range(0, n + 1):
	for letter in chars:
		for j in charIndexes[letter]:
			if dpl[i][j] + dpr[n - i][m - j - 1] == lcs:
				ans += 1
				break
print(ans)


M = 62

def func(c):
	if c >= 'a' and c <= 'z':
		return ord(c) - 97
	if c >= 'A' and c <= 'Z':
		return ord(c) - 65
	return ord(c) - 48

def tutzkiAndLcs(a, b):
	n = len(a)
	m = len(b)
	dp = []
	dpr = []
	position = [[] for i in range(M)]
	for i in range(1, m + 1, 1):
		position[func(b[i - 1])].append(i)
	for i in range(n + 2):
		dp += [[0] * (m + 2)]
		dpr += [[0] * (m + 2)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if a[i - 1] == b[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	for i in range(n, 0, -1):
		for j in range(m, 0, -1):
			if a[i - 1] == b[j - 1]:
				dpr[i][j] = 1 + dpr[i + 1][j + 1]
			else:
				dpr[i][j] = max(dpr[i + 1][j], dpr[i][j + 1])
	ans = 0
	for i in range(0, n + 1, 1):
		for c in range(0, 26, 1):
			for j in range(0, len(position[c]), 1):
				p = position[c][j]
				if dp[i][p - 1] + dpr[i + 1][p + 1] == dp[n][m]:
					ans += 1
					break
	print(ans)
s1 = input()
s2 = input()
tutzkiAndLcs(s1, s2)