题目描述：
给定两个字符串s1和s2，计算其最长公共子串的长度，并返回所有可能的最长公共子串。

# -*- coding: utf-8 -*-# @Time : 2019-09-22 22:57# @Author : Jayce Wong# @ProjectName : job# @FileName : longestCommonSubstring.py# @Blog : https://blog.51cto.com/jayce1111# @Github : https://github.com/SysuJaycedef lcs(s1, s2): """ 现在我们知道了，如果遇到输入是两个字符串的，需要用到的动态规划的话，那么我们需要的状态是一个 二维的矩阵。 首先我们需要定义这个矩阵中每个元素的意义： dp[i][j]代表了s1[: i + 1]和s2[: j + 1]以s1[i]和s2[j]结尾的公共子串的长度。 那么关键就在于如何确定转换方程和如何初始化这个状态矩阵了。 显然，由于dp[i][j]计算的是同时以s1[i]和s2[j]为结尾公共子串的长度， 如果s1[i] != s2[j]，那么dp[i][j] = 0 当s1[i] == s2[j]时，dp[i][j] = dp[i - 1][j - 1] + 1 :param s1: 输入的第一个字符串 :param s2: 输入的第二个字符串 :return: 最大公共子串长度、以及最大公共子串的具体值 """ # 为了方便编程，先在s1和s2前面加入一个空格占位 s1 = ' ' + s1 s2 = ' ' + s2 rows = len(s1) cols = len(s2) dp = [[0] * cols for _ in range(rows)] maxlen = 0 for i in range(1, rows): for j in range(1, cols): if s1[i] == s2[j]: dp[i][j] = dp[i - 1][j - 1] + 1 maxlen = max(maxlen, dp[i][j]) else: dp[i][j] = 0 res = [] for i in range(1, rows): for j in range(1, cols): # s1[i]为结尾的子串，截取长度为maxlen即可 if dp[i][j] == maxlen: res.append(s1[i - maxlen + 1: i + 1]) return maxlen, resdef main(): s1 = 'ABCBDEFBWD' s2 = 'BCBWD' maxlen, res = lcs(s1, s2) print(maxlen) print(res)if __name__ == '__main__': main()