題目：

　　給定兩個字符串str1和str2，返回兩個字符串的最長公共子串。

舉例：

　　str1 = “1AB2345CD”，str2 = “12345EF”，返回”2345”。

基本思路：

　　假設str1的長度為N，str2的長度為M，生成N×M的矩陣dp，dp[i][j]的含義是必須以str1[i]和str2[j]結尾的最長公共子串的長度，dp[i][j]的計算方法如下：

　　１．矩陣的第一行。如果str1[0] == str2[j]，此時以str1[0]和str2[j]結尾的最長公共子串就是它們自身，dp[0][j]設為1。　?
　　２．矩陣的第一列。如果str1[i] == str2[0]，dp[i][0]設為1。　　?
　　３． 矩陣的其它位置計算如下：?
　　　１）如果str1[i] != str2[j]，說明以str1[i]和str2[j]結尾的子串是不存在的，設為0。?
　　　２） 如果str1[i] == str2[j]，說明str1[i]和str2[j]可以作為公共子串的最后一個字符，從最后一個字符向左能擴多大的長度呢？就是dp[i-1][j-1]的值，所以dp[i][j] = dp[i-1][j-1] + 1。

　　生成dp表之后，再得到最長的公共子串就很容易了。?
　　dp表中的最大值（假設為dp[x][y]）就是最長公共子串的長度（假設為maxlen），str1中從下標x開始向左數的maxlen個字符就是最長的公共子串。

　　因為dp[i][j]的值只依賴于dp[i-1][j-1]，所以可以用空間壓縮的方法將空間復雜度從Ｏ(N*M)降低到Ｏ(1)。
?

"""經典動態規劃方法，時間復雜度O(M*N),空間復雜度O(M*N)"""def getdp(str1,str2):dp = [[0 for i in range(len(str2))] for j in range(len(str1))]for i in range(len(str1)):dp[i][0] = 1 if str1[i] == str2[0] else 0for j in range(len(str2)):dp[0][j] = 1 if str2[j] == str1[0] else 0for i in range(1,len(str1)):for j in range(1,len(str2)):if str1[i] == str2[j]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = 0return dpdef lcst(str1,str2):if str1 == None or str2 == None or str1 == '' or str2 == '':return None"""max代表最長公共子串的長度"""max_ = 0index = 0for i in range(len(str1)):for j in range(len(str2)):if dp[i][j] > max:max_ = dp[i][j]index = ireturn str1[index-max_+1,index+1]"""空間壓縮的辦法，時間復雜度為O(M*N), 空間復雜度O(1)"""def lcst2(str1,str2):if str1 == None or str2 == None or str1 == '' or str2 == '':return ''row = 0col = len(str2)-1max_ = 0end = 0while row < len(str1):i = rowj = collen_ = 0while i < len(str1) and j < len(str2):if str1[i] != str2[j]:len_ = 0else:len_ +=1if len_ > max_:end = imax_ = len_i +=1j +=1if col > 0:col -= 1 //斜線位置的列向左移動else:row += 1 //列移動到最左之后，行向下移動return str1[end-max_+1:end+1]

?

總結

以上是生活随笔為你收集整理的最长公共子串问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。