189 8069 5689
题目描述：
给定两个字符串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/SysuJayce
def 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, res
def main():
s1 = 'ABCBDEFBWD'
s2 = 'BCBWD'
maxlen, res = lcs(s1, s2)
print(maxlen)
print(res)
if __name__ == '__main__':
main()