动态规划求最长公共子串步骤

动态规划求最长公共子串的步骤如下：
1. 初始化一个二维数组dp，其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。
2. 遍历两个字符串，如果第一个字符串的第i个字符和第二个字符串的第j个字符相等，则dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。
3. 在遍历的过程中，记录最长的公共子串的长度和结束位置。
4. 根据结束位置和最长公共子串的长度，可以得到最长公共子串。

下面是一个Python实现的例子：

def longest_common_substring(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len, end_pos = 0, 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0
    return str1[end_pos - max_len:end_pos], max_len