题解 | 查找两个字符串a,b中的最长公共子串

def find_longest_common_substring(a, b):
    # 获取字符串长度
    m, n = len(a), len(b)
    
    # 初始化 DP 数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 记录最长子串的长度和结束位置
    max_length = 0
    end_pos = 0  # 在字符串 a 中的结束位置

    # 填充 DP 数组
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:  # 如果字符相同
                dp[i][j] = dp[i - 1][j - 1] + 1
                # 更新最大长度和结束位置
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0  # 不相同则置为 0

    # 提取最长公共子串
    longest_common_substring = a[end_pos - max_length:end_pos]
    return longest_common_substring


# 示例
a = input()
b = input()
if len(a) > len(b):
    a, b = b, a
result = find_longest_common_substring(a, b)
print(result)

思路：

动态规划可以高效解决最长公共子串问题。

1. 创建一个二维数组 dp，其中 dp[i][j] 表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符中，以 a[i-1] 和 b[j-1] 结尾的最长公共子串的长度。
2. 如果 a[i-1] == b[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
3. 如果 a[i-1] != b[j-1]，则 dp[i][j] = 0；
4. 在遍历过程中，记录最长长度及其结束位置，然后根据结束位置提取最长公共子串。

例如a字串：babcde，b字串：abcda，结果如下