最长公共子串，动态规划，时间O(mn)，空间O(min(m,n)*k), k为最长公共子序列长度（超时）

分析过程类似于：https://www.nowcoder.com/discuss/388075528203378688
公共子串条件是：同时含有并且连续（[s1[i-1], s1[i]]与[s2[j-1], s1[j]]连续），存在很多局部情况，所以原问题的解不一定包含所有子问题的解，直接以最长公共子串为状态不好互相转换。以包含（i,j）点值的局部公共子串为状态，再维护一个最大最长公共子串。遍历m*n空间搜索满足条件的点，如果s1[i]=s2[j]，则同时含有的条件满足，现在只需要找到与之连续的最近已知点(i-1, j-1)，并把（i,j）点值加入(i-1, j-1)点状态（公共子串）中，得到（i,j）点状态，即dp[i][j]=dp[i-1][j-1] + s1[i]。如果s1[i]!=s2[j]，即同时含有不满足，它不含于任何公共子串，为''，即dp[i][j]=''

由于每一行的状态只与上一行有关，可以优化dp为一维向量，但此时需要一个变量来记录(i-1, j-1)状态。

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        if len(str1) > len(str2):
            str1, str2 = str2, str1    # str1为小串
        m, n = len(str1), len(str2)
        dp = ['']*(m+1)                # dp[0]是不更新的占位状态，便于计算边缘出的状态值
        max_str = ''                   # 维护一个最大公共子串
        for i in range(n):
            pre_dp = dp[0]
            for j in range(m):         # 根据短串更新dp
                if str1[j] == str2[i]:
                    tmp = dp[j+1]      # 记录下一个点的(i-1,j-1)状态
                    dp[j+1] = pre_dp + str1[j] # 状态转移
                    pre_dp = tmp
                else:
                    pre_dp = dp[j+1]      # 记录下一个点的(i-1,j-1)状态
                    dp[j+1] = ''          # 清空状态
                if len(max_str) < len(dp[j+1]):
                    max_str = dp[j+1]
        return max_str