题解 | #最长公共子序列(一)#

n, m = map(int, input().split())
a = input()
b = input()
if n > m:
    n, m, = m, n
    a, b = b, a
row = [0] * n
col = [0] * m
for i in range(n):
    row[i] = 1 if b[0] in a[:i+1] else 0
for i in range(m):
    col[i] = 1 if a[0] in b[:i+1] else 0

pre = row.copy()
res = [0] * n
for i in range (1, m):
    for j in range(n):
        if j == 0:
            res[j] = col[i]
        else:
            if a[j] == b[i]:
                res[j] = pre[j-1] + 1
            else:
                res[j] = max(res[j-1], pre[j])
    pre = res.copy()
print(res[-1])