編輯距離，最長公共子序列，最長公共子串，最長遞增子序列

編輯距離，又稱Levenshtein距離（也叫做Edit Distance），是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個字元替換成另一個字元，插入一個字元，删除一個字元。俄羅斯科學家Vladimir Levenshtein在1965年提出這個概念。

例如将kitten一字轉成sitting：

sitten （k→s）

sittin （e→i）

sitting （→g）

View Code

二維數組最後一個元素值就是最小編輯距離，也就是6.

最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分别是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。而最長公共子串(要求連續)和最長公共子序列是不同的，因為最長公共子序列不要求子序列在原有序列中連續出現。

這種題目使用動态規劃解決。為了節約重複求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存于該數組中，這就是動态規劃法所采用的基本方法。是以此處引進一個二維數組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長度，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的，以決定搜尋的方向。

我們首先進行自底向上的遞推計算，那麼在計算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計算出來。此時我們根據X[i] = Y[j]還是X[i] != Y[j]，就可以計算出c[i][j]。具體思路如下

我們上面的自底向上推算是在“c[i-1][j-1]，c[i-1][j]與c[i][j-1]已經計算出來後再求c[i,j]”這個前提下進行的。是以我們建構c[][]這個數組是從頭開始的。在建立好c[][]以後我們需要初始化這個二維數組，c[0][0...n]=0，c[0...m][0]=0。這是為了便于計算後面的c[1][1]使用。用于表示x[1]和y[1]的最長公共子序列，但是我們發現字元數組char* x[]跟char* y[]是從下标0開始計算的，是以在這裡x[i][j]表示的是x[i-1]和y[j-1]的最長公共子序列。

最後問題可以用遞歸式寫成：

根據上述解題思路給出代碼實作

上述代碼隻給出了最長公共子序列的長度，但是沒有輸出最長公共子序列，如前所述我們需要通過一個b[][]來記錄c[][]是由哪一步得到的。

b[i][j]=0;//表示c[i][j]由c[i-1][j-1]+1得到

b[i][j]=1;//表示c[i][j]由c[i][j-1]得到

b[i][j]=-1;//表示c[i][j]由c[i-1][j]得到

這樣在輸出最長子序列的時候，我們從c[][]最後一個位置開始遞歸周遊。代碼實作如下：

3.1解體思路

找兩個字元串的最長公共子串，這個子串要求在原字元串中是連續的。可以用動态規劃來求解。我們采用一個二維矩陣來記錄中間的結果。這個二維矩陣怎麼構造呢？首先初始化這個二維數組c[][]，

如果x[0..i]=y[0]，則c[i][0]=1，否則c[i][0]=0

如果y[0..j]=x[0]，則c[0][j]=1，否則c[0][j]=0

然後計算c[i][j]的值，如果x[i]==y[j]，則c[i][j]=c[i-1][j-1]+1。

直接舉個例子吧："ABCBDAB"和"BDCABA"(當然我們現在一眼就可以看出來最長公共子串是"AB"或"BD")

<a></a>

3.2代碼實作

<a href="http://blog.csdn.net/hhygcy/article/details/3950158">http://blog.csdn.net/hhygcy/article/details/3950158</a>

既然已經說到了最長公共子序列，就把這個遞增子序列也說了。同樣的，這裡subsequence表明了這樣的子序列不要求是連續的。比如說有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }，這樣一個字元串的的最長遞增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。

其實這個問題和前面的最長公共子序列問題還是有一定的關聯的。

假設我們的初始的序列                 S1= {1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1,    7 }。

那我們從小到大先排序一下。得到了S1'={1, 1, 3, 4, 4,   5, 6, 7, 7 , 8,  9, 11, 19}。

這樣我們再求S1和S1'的最長公共子序列就是S1的最長遞增子序列了。這個過程還是比較直覺的。但是這個不是這次要說的重點，這個問題有比較傳統的做法的.

我們定義L(j)是一個優化的子結構,也就是最長遞增子序列。那麼L(j)和L(1..j-1)的關系可以描述成

L(j) = max {L(i), i&lt;j &amp;&amp; Ai&lt;Aj  } + 1;  也就是說L(j)等于之前所有的L(i)中最大的的L(i)加一。這樣的L(i)需要滿足的條件就是Ai&lt;Aj。這個推斷還是比較容易了解的。就是選擇j之前所有的滿足小于目前數組的最大值。

最後求max(L(j))就是最長遞增子序列，需要注意的是L[len-1]并不一定是最長遞增子序列的長度。

但是上面的 LIS和 LIS2兩種實作都沒有給出遞增子序列本身，隻給出了長度。而 LIS3能夠輸出一個子序列。舉例說明其實作方式:

如上述所示，我們首先初始化數組L[]和p[]，其中L用于記錄遞增子序列的長度，而p[]用于回溯遞增子序列，其中p[j]=i表示arry[i]-&gt;arry[j]是一個遞增子序列。我們在L[]中能夠求出遞增子序列的長度max以及遞增子序列的末尾元素所在位置k。然後通過k我們回溯數組p，是以這裡使用了遞歸方式列印遞增子序列。

本文轉自xwdreamer部落格園部落格，原文連結：http://www.cnblogs.com/xwdreamer/archive/2011/06/21/2296995.html，如需轉載請自行聯系原作者