Find the length of the longest subsequence common to two strings. A subsequence keeps order but may skip characters (it need not be contiguous).
Two lines: the string s, then the string t.
The length of their longest common subsequence.
Example 1
abcde ace
3
The subsequence "ace" has length 3.
Example 2
abc abc
3
Identical strings — length 3.
Example 3
abc def
0
Nothing in common — 0.
Let dp[i][j] be the LCS length of the first i characters of s and the first j of t.
If s[i-1] == t[j-1] then dp[i][j] = dp[i-1][j-1] + 1; otherwise it is max(dp[i-1][j], dp[i][j-1]).
Classic DP grid: extend the diagonal on a character match, otherwise carry the better of dropping one character from either string.
import sys
lines = sys.stdin.read().split('\n')
a = lines[0] if len(lines) > 0 else ''
b = lines[1] if len(lines) > 1 else ''
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 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])
print(dp[m][n])
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.