最長公共子串

題目描述：
給定兩個(gè)字符串s1和s2，計(jì)算其最長公共子串的長度，并返回所有可能的最長公共子串。

# -*- 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):
    """
    現(xiàn)在我們知道了，如果遇到輸入是兩個(gè)字符串的，需要用到的動(dòng)態(tài)規(guī)劃的話，那么我們需要的狀態(tài)是一個(gè)
    二維的矩陣。
    首先我們需要定義這個(gè)矩陣中每個(gè)元素的意義：
    dp[i][j]代表了s1[: i + 1]和s2[: j + 1]以s1[i]和s2[j]結(jié)尾的公共子串的長度。
    那么關(guān)鍵就在于如何確定轉(zhuǎn)換方程和如何初始化這個(gè)狀態(tài)矩陣了。

    顯然，由于dp[i][j]計(jì)算的是同時(shí)以s1[i]和s2[j]為結(jié)尾公共子串的長度，
    如果s1[i] != s2[j]，那么dp[i][j] = 0
    當(dāng)s1[i] == s2[j]時(shí)，dp[i][j] = dp[i - 1][j - 1] + 1
    :param s1: 輸入的第一個(gè)字符串
    :param s2: 輸入的第二個(gè)字符串
    :return: 最大公共子串長度、以及最大公共子串的具體值
    """
    # 為了方便編程，先在s1和s2前面加入一個(gè)空格占位
    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]為結(jié)尾的子串，截取長度為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()