最长公共子序列(一)

n,m = list(map(int,input().split()))
s1=input()
s2=input()
shorterLength = min(n,m)
longerLength = max(n,m)
# 空间复杂度O(mn)
# dp = [[0]*(longerLength+1) for i in range(shorterLength+1)]
# if shorterLength==m:
#     s1,s2 = s2,s1
# for i in range(1,shorterLength+1):
#     for j in range(1,longerLength+1):
#         if s1[i-1]==s2[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[shorterLength][longerLength])

# 空间复杂度O(min(m,n))
dp1 = [0]*(shorterLength+1)
dp2 = [0]*(shorterLength+1)
if shorterLength==m:
    s1,s2 = s2,s1
for i in range(1,longerLength+1):
    for j in range(1,shorterLength+1):
        if s2[i-1]==s1[j-1]:
            dp2[j]=dp1[j-1]+1
        else:
            dp2[j]=max(dp2[j-1],dp1[j])
    dp1 = dp2.copy()
print(dp2[shorterLength])

import sys

i = 0
m = n = 0
s1 = s2 = ""
for line in sys.stdin:
    a = line.split()
    if i == 0:
        m, n = int(a[0]), int(a[1])
    elif i == 1:
        s1 = a[0]
    else:
        s2 = a[0]
    i += 1
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

for i in range(m):
    for j in range(n):
        if s1[i] == s2[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
print(dp[m][n])