最长公共子序列和最长公共子串(python)

最长公共子序列（Longest Common Subsequence, LCS）和最长公共子串（Longest Common Substring）是两个常见的字符串相关问题。

最长公共子序列是指给定两个字符串，要求找到它们之间最长的公共子序列的长度。子序列是从原字符串中删除若干个字符而得到的新字符串，字符在新字符串中的相对顺序与原字符串中的保持一致。动态规划是求解LCS问题的常用方法。

以字符串s1 = "ABCBDAB"和s2 = "BDCAB"为例，可以使用动态规划的方法求解最长公共子序列的长度。首先创建一个二维数组dp，dp[i][j]表示s1的前i个字符和s2的前j个字符之间的最长公共子序列的长度，那么有以下推导关系：

1. 当i=0或j=0时，dp[i][j]=0。
2. 当s1[i-1]=s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1。
3. 当s1[i-1]!=s2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最后，dp[len(s1)][len(s2)]即为最长公共子序列的长度。

对于最长公共子串，要求找到两个字符串中最长的公共连续子串的长度。连续子串是指在原字符串中连续出现的字符子序列。同样可以使用动态规划来解决该问题。

仍以上述两个字符串s1和s2为例，创建一个二维数组dp，dp[i][j]表示以s1[i-1]和s2[j-1]为结尾的公共子串的长度，那么有以下推导关系：

1. 当i=0或j=0时，dp[i][j]=0。
2. 当s1[i-1]=s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1。
3. 当s1[i-1]!=s2[j-1]时，dp[i][j] = 0。

最后，dp矩阵中的最大值即为最长公共子串的长度。

以上就是求解最长公共子序列和最长公共子串的常见方法。在实际应用中，我们可以根据具体的问题选择合适的方法，并结合动态规划来解决这些字符串相关的问题。