给出2个字符串，输出2字符串的最长公共子串。

### 回答1：
输入：两个字符串

输出：最长公共子串

算法：

1. 定义两个字符串s1和s2，分别表示输入的两个字符串。

2. 定义一个二维数组dp，dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子串长度。

3. 初始化dp数组，dp[0][j]和dp[i][0]都为0。

4. 遍历s1和s2的每个字符，如果s1[i]等于s2[j]，则dp[i][j]等于dp[i-1][j-1]+1，否则dp[i][j]等于0。

5. 在遍历过程中记录最长公共子串的长度和结束位置。

6. 根据最长公共子串的长度和结束位置，从s1中截取最长公共子串并返回。

代码实现：

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    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 s1[i - 1] == s2[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 s1[end_pos - max_len:end_pos]

示例：

s1 = "abcdefg"
s2 = "defghij"
print(longest_common_substring(s1, s2))  # "def"

### 回答2：
最长公共子串指两个字符串中的共同连续串，也就是说，在两个字符串中找到一个共同的最长的子串。这个问题可以用动态规划算法来解决。

首先，我们创建一个二维数组来存储最长公共子串的长度。设数组L[i][j]表示字符串str1前i个字符和字符串str2前j个字符的最长公共子串长度。如果str1[i]和str2[j]相等，L[i][j] = L[i-1][j-1] + 1；否则，L[i][j] = 0。

接下来，我们在L数组中查找最大的值，以及对应的位置，即最长公共子串的结束位置。设max为L数组中的最大值，则最长公共子串的长度为max。对于位置(x,y)，我们可以通过回溯L数组来找到最长公共子串的起始位置。

最后，我们可以将最长公共子串输出即可。

下面是示例代码：

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    L = [[0] * (n+1) for i in range(m+1)]
    maxLen = 0
    endPos = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                L[i][j] = L[i-1][j-1] + 1
                if L[i][j] > maxLen:
                    maxLen = L[i][j]
                    endPos = (i-1,j-1)
    startPos = (endPos[0]-maxLen+1, endPos[1]-maxLen+1)
    return str1[startPos[0]:endPos[0]+1]

# 测试代码
str1 = "abcdefg"
str2 = "cdefghijk"
print(longest_common_substring(str1, str2)) # 输出 "cdefg"

总之，用动态规划算法可以有效地解决最长公共子串的问题，是一种常用的算法。

### 回答3：
最长公共子串是指2个字符串中同时出现的最长子串。在解决这个问题时，我们可以采用动态规划算法来解决。

假设给出的两个字符串是S1和S2，我们需要找出它们的最长公共子串。我们定义一个二维数组dp[i][j]，其中dp[i][j]表示字符串S1从i开始到结尾的子串和字符串S2从j开始到结尾的子串的最长公共子串的长度。这个数组的大小是(len(S1)+1)*(len(S2)+1)，其中len(S1)和len(S2)分别表示两个字符串的长度。

接下来我们考虑如何推导这个数组。对于dp[i][j]，如果S1[i]==S2[j]，则dp[i][j]=dp[i+1][j+1]+1，表示最长公共子串增加了1；否则dp[i][j]=0，表示当前子串中没有公共字符。

在推导完成dp数组之后，我们需要找到最大的dp[i][j]，即最长公共子串的长度，以及对应位置的索引。实现这一步的代码如下：

max_len = 0
max_index = 0
for i in range(len(S1)):
    for j in range(len(S2)):
        if S1[i] == S2[j]:
            dp[i][j] = dp[i+1][j+1] + 1
            if dp[i][j] > max_len:
                max_len = dp[i][j]
                max_index = i
        else:
            dp[i][j] = 0

最后，我们可以从max_index开始往前找max_len个字符即为最长公共子串。实现这一步的代码如下：

result = ''
for i in range(max_index, max_index+max_len):
    result += S1[i]
print(result)

这样，我们就成功地解决了从两个字符串中找到最长公共子串的问题。