寫(xiě)在前面

首先解釋一下二者的區(qū)別，最長(zhǎng)公共子序列(LCS)允許兩個(gè)公共的子序列在原有的兩個(gè)字符串中不連續(xù)，即ABCFD與EACFB，二者的最長(zhǎng)公共子序列為ACF；而最長(zhǎng)公共子串伍掀，要求連續(xù)，其最長(zhǎng)公共子串為CF暇藏。

1. 最長(zhǎng)公共子序列

描述：給出兩個(gè)字符串蜜笤，找到最長(zhǎng)公共子序列(LCS)，返回LCS的長(zhǎng)度盐碱。
題目鏈接：https://www.lintcode.com/problem/longest-common-subsequence/description

最長(zhǎng)公共子序列的定義：：
最長(zhǎng)公共子序列問(wèn)題是在一組序列（通常2個(gè)）中找到最長(zhǎng)公共子序列（注意：不同于子串把兔，LCS不需要是連續(xù)的子串）。該問(wèn)題是典型的計(jì)算機(jī)科學(xué)問(wèn)題瓮顽，是文件差異比較程序的基礎(chǔ)垛贤，在生物信息學(xué)中也有所應(yīng)用。
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

樣例 1:
    輸入:  "ABCD" and "EDCA"
    輸出:  1
    
    解釋:
    LCS 是 'A' 或  'D' 或 'C'

樣例 2:
    輸入: "ABCD" and "EACB"
    輸出:  2
    
    解釋: 
    LCS 是 "AC"

思路：
這種雙序列動(dòng)態(tài)規(guī)劃的題目趣倾，一般是考慮如下幾種情況：

1. 最后一步和子問(wèn)題：
   • 字符串A和字符串B的最后一個(gè)元素不相同聘惦，那其公共子序列需要用A[:n - 1] 和B或者**A和B[m - 1]去找。
   • 字符串A和字符串B的最后一個(gè)元素 相同儒恋，那其公共子序列需要用A[:n - 1] 和[m - 1]去找善绎。

2. 轉(zhuǎn)移方程：
   使用一個(gè)二維矩陣去記錄兩個(gè)字符串的子序列之間最大公共子序列長(zhǎng)度。

   
   
   image
3. 初始條件及邊界條件：
   當(dāng)序列為空是诫尽，與其他子序列的公共子序列長(zhǎng)度為空禀酱。因此，需要再加一維牧嫉，記錄空序列的長(zhǎng)度(即剂跟，長(zhǎng)度為0)减途。
4. 計(jì)算順序
   從上到下，從左到右曹洽。
   
   image.png
   
   代碼實(shí)現(xiàn)：

class Solution:
    """
    @param A: A string
    @param B: A string
    @return: The length of longest common subsequence of A and B
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if A == '' or B == '':
            return 0
        n = len(A)
        m = len(B)
        dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

1.1 進(jìn)階

還原最長(zhǎng)公共子序列鳍置，也就是把公共子序列打印出來(lái)。
這里需要再追加一個(gè)輔助數(shù)組flags數(shù)組送淆，這個(gè)數(shù)組的維度和剛才的dp數(shù)組相同税产。這個(gè)數(shù)組主要是用來(lái)記錄dp數(shù)組的每一步都執(zhí)行了什么操作。用3來(lái)表示A[i - 1] == B[j - 1]偷崩，用1來(lái)表示dp[i][j] = dp[i - 1][j]辟拷，用2來(lái)表示dp[i][j] = dp[i][j - 1]。我們從最后一個(gè)元素開(kāi)始還原，就是需要找到標(biāo)記為3的坐標(biāo)位置，然后根據(jù)A或者B還原出公共子序列汇陆。
具體代碼如下：

class Solution:
    """
    @param A: A string
    @param B: A string
    @return: The length of longest common subsequence of A and B
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if A == '' or B == '':
            return 0
        n = len(A)
        m = len(B)
        dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
        flags = [[0 for j in range(m + 1)] for i in range(n + 1)] # 輔助標(biāo)記數(shù)組
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    flags[i - 1][j - 1] = 3
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                    if dp[i - 1][j] == dp[i][j]:
                        flags[i - 1][j] = 1 
                    else:
                        flags[i][j - 1] = 2
        s = ['' for i in range(dp[n][m])]
        p = dp[n][m] - 1
        row = n
        col = m
        while row > 0 and col > 0:
            if flags[row][col] == 1:
                row -= 1
            elif flags[row][col] == 2:
                col -= 1
            else:
                s[p] = A[row - 1]
                p -= 1
                row -= 1
                col -= 1

        return s

if __name__ == '__main__':
    s = Solution()
    A = 'abcd'
    B = 'wwawwbwwdwwwcwwd'
    print(s.longestCommonSubsequence(A,B))

2. 最長(zhǎng)公共子串

題目鏈接：https://www.lintcode.com/problem/longest-common-substring/description
題目描述：給出兩個(gè)字符串，找到最長(zhǎng)公共子串隅俘，并返回其長(zhǎng)度。
樣例 1:
輸入: "ABCD" and "CBCE"
輸出: 2

解釋:
最長(zhǎng)公共子串是 "BC"

樣例 2:
輸入: "ABCD" and "EACB"
輸出: 1

解釋: 
最長(zhǎng)公共子串是 'A' 或 'C' 或 'B'

• 給出一個(gè)時(shí)間復(fù)雜度為O(n^2)的解法,這種方法效率太低到推。

class Solution:
    """
    @param A: A string
    @param B: A string
    @return: the length of the longest common substring.
    """
    def longestCommonSubstring(self, A, B):
        # write your code here
        if A == '' or B == '':
            return 0
        max_len = 0
        for i in range(len(A)):
            for j in range(i, len(A)):
                s = A[i:j+1]
                if s in B:
                    max_len = max(max_len, len(s))
        return max_len

• 下面給出優(yōu)化：
  和最長(zhǎng)公共子序列的做法基本一致考赛，只是有了連續(xù)的要求惕澎，因此莉测，狀態(tài)轉(zhuǎn)移方程需要改一下：
  
  image.png
  
  而且返回的也是最后一個(gè)結(jié)果了，需要一個(gè)max_length變量來(lái)記錄最大長(zhǎng)度唧喉。

class Solution:
    """
    @param A: A string
    @param B: A string
    @return: the length of the longest common substring.
    """
    def longestCommonSubstring(self, A, B):
        # write your code here
        if A == '' or B == '':
            return 0
        n = len(A)
        m = len(B)
        dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
        max_length = 0
        for i in range(1, n+1):
            for j in range(1, m+1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = 0
                max_length = max(max_length, dp[i][j])
        return max_length