最長公共子串

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

創(chuàng)新互聯(lián)建站堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的黑龍江網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

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

    顯然，由于dp[i][j]計算的是同時以s1[i]和s2[j]為結(jié)尾公共子串的長度，
    如果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]為結(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()

網(wǎng)頁題目：最長公共子串
當前URL：http://bm7419.com/article18/pscedp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、企業(yè)建站、手機網(wǎng)站建設(shè)、建站公司、網(wǎng)站設(shè)計、虛擬主機

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)