Algorithm：C++/python語言實現之求旋轉數組最小值、求零子數組、求最長公共子序列和最長公共子串、求LCS與字符串編輯距離

?

?

目錄

? 一、求旋轉數組最小值 ?

1、分析問題

2、解決思路

二、求零子數組

1、算法思路

2、要說明的兩個問題

三、最長公共子串和最長公共子序列

1、最長公共子串(必須連續)—python實現

2、最長公共子序列(可不連續)—python實現

2、LCS的意義

3、求解

4、LCS的應用—最長遞增子序列LIS

5、LIS的動態規化算法

四、LCS與字符串編輯距離

---

?

?

? 一、求旋轉數組最小值 ?

? ? ? ?假定一個排序數組以某個未知元素為支點做了旋轉，如：原數組0 1 2 4 5 6 7旋轉后得到4 5 6 7 0 1 2。請找出旋轉后數組的最小值。假定數組中沒有重復數字。

1、分析問題

? ? ? ? 旋轉之后的數組實際上可以劃分成兩個有序的子數組：前面子數組的大小，都大于后面子數組中的元素；4 5 6 7 0 1 2 注意到，實際上最小的元素就是兩個子數組的分界線。

2、解決思路

? ? ? ? 用兩個指針low、high分別指向數組的第一個元素和最后一個元素。如果是正常的排序數組(元素間不重復)，第一個元素肯定小于最后一個元素。
? ? ? ?計算中間位置mid = (low+high)/2。
(1)、先考察A[mid]、A[low]關系
? ? ? ?若：A[mid]>A[low]，則A[low,low+1….mid-1,mid]是遞增序列，最小元素位于子數組A[mid+1,mid+2,…high]中。因此，做賦值low=mid+1。
? ? ? ?若：A[mid]<A[low] ，則A[low,low+1….mid-1,mid]不是遞增序列，即：中間元素該子數組中，做賦值high=mid。
(2)、再考察A[mid]、A[high]關系
? ? ? ?對偶地，若考察A[mid]與A[high]的關系，能夠得到相似的結論。

?

二、求零子數組

? ? ? 求對于長度為N的數組A，求子數組的和接近0的子數組，要求時間復雜度O(NlogN)。

1、算法思路

? ? ? 申請同樣長度的空間sum[0…N-1]，sum[i]是A的前i項和。
Trick：定義sum[-1] = 0
顯然有：
算法：對sum[0…N-1]排序，然后計算sum相鄰元素的差，最小值記為min1。
? ? ? ?min1：在A中任意取兩個集合，各自元素的和求差的最小值
? ? ? ?因為sum[-1]=0，sum[0…N-1]的絕對值最小值記為min2。
? ? ? ?min2：A的前k個元素的和的絕對值的最小值
? ? ? ?min1和min2的更小者，即為所求。

2、要說明的兩個問題

sum本身的計算和相鄰元素差的計算，都是O(N)，sum的排序是O(NlogN)，因此，總時
間復雜度：O(NlogN)
強調：除了計算sum相鄰元素的差的最小值，別忘了sum自身的最小值。一個對應A[i…j]，一個對應A[0…j]

?

三、最長公共子串和最長公共子序列

1、最長公共子串(必須連續)—python實現

? ? ? ?Longest Common Substring最長公共子串。

def LCS_find_Substring(s1, s2): #求兩個字符串最長公共子串'''用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，若是匹配則為1,否則為0。然后求出對角線最長的1的序列，其對應的位置就是最長匹配子串的位置。'''matrix_2D=[ [0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #定義全0矩陣，為方便后續計算，比字符串長度多了一列 # print('生成(i+1)行、(j+1)列全0矩陣：',matrix_2D)length_max=0 #最長匹配的長度p_end=0 #最長匹配對應在s1中的最后一位for i in range(len(s1)):for j in range(len(s2)):if s1[i]==s2[j]: #第一個if判斷，兩字符串內元素對應相等時，矩陣內，再次相等元素處的索引累計+1matrix_2D[i+1][j+1]=matrix_2D[i][j]+1if matrix_2D[i+1][j+1]>length_max: #第二個if判斷，將當前相等元素的個數，賦值給length_maxlength_max=matrix_2D[i+1][j+1]p_end=i+1 #記錄s1中連續相等情況下，最后的索引位置print(matrix_2D)print(p_end,length_max)return s1[p_end-length_max:p_end],length_max #返回最長子串及其長度s1=str(input()) s2=str(input()) res=LCS_find_Substring(s1, s2) print(res)

?

2、最長公共子序列(可不連續)—python實現

? ? ? ?Longest Common?Subsequence，LCS 一個序列S任意刪除若干個字符得到新序列T，則T叫做S的子序列；兩個序列X和Y的公共子序列中，長度最長的那個，定義為X和Y的最長公共子序列。
? ? ? 比如：字符串"helloworld"和"loop"的最長公共子序列為loo；字符串acdfg與adfc的最長公共子序列為adf。
注意：區別最長公共子串，最長公共字串要求連續，而序列可以不連續。

def LCSubsequence(string1,string2):len1 = len(string1)len2 = len(string2)res = [[0 for i in range(len1+1)] for j in range(len2+1)]for i in range(1,len2+1):for j in range(1,len1+1):if string2[i-1] == string1[j-1]:res[i][j] = res[i-1][j-1]+1else:res[i][j] = max(res[i-1][j],res[i][j-1])return res,res[-1][-1] print(LCS("helloworld","loop"))

?

?

?

?

?

2、LCS的意義

(1)、求兩個序列中最長的公共子序列算法，廣泛的應用在圖形相似處理、媒體流的相似比較、計算生物學方面。生物學家常常利用該算法進行基因序列比對，由此推測序列的結構、功能和演化過程。
(2)、LCS可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來辨別抄襲。另一方面，對一段文字進行修改之后，計算改動前后文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準確。簡而言之，百度知道、百度百科都用得上。

?

3、求解

(1)、計算LCS長度

(2)、根據b提供的方向，構造最長公共子序列

?

(3)、最大公共子序列的多解性：求所有的LCS

4、LCS的應用—最長遞增子序列LIS

T1、使用LCS解LIS問題
T2、使用動態規劃來求解

?

5、LIS的動態規化算法

?

?

四、LCS與字符串編輯距離

1、字符串“ALGORITHM”是如何變成字符串“ALTRUISTIC”的？

?

參考文獻
余祥宣等，計算機算法基礎[M]，華中科技大學出版社，2001
劉佳梅.求最長公共子序列問題的一種快速算法.中國科技論文在線[J].2010,11
李欣，舒風迪.最長公共子序列問題的改進快速算法.計算機應用研究[J].2000
鄭翠玲.最長公共子序列算法的分析與實現.武夷學院學報[J],2010,29 卷(2):44~48
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md(最大子數組)
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.02.md(字符串編輯距離)

?

?

?

總結

以上是生活随笔為你收集整理的Algorithm：C++/python语言实现之求旋转数组最小值、求零子数组、求最长公共子序列和最长公共子串、求LCS与字符串编辑距离的全部內容，希望文章能夠幫你解決所遇到的問題。

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