決定什麼是LCS算法

的序列我已經STUDING的最後一個星期的LCS的問題，我有一個問題。我們創建一個輔助字符串（string1.length X string2.length），通過向上累加箭頭來確定子序列是什麼，左邊的是什麼箭頭或對角箭頭，對應於我們來自哪裏，所以我們可以稍後回顧我們的步驟並找到子序列本身。決定什麼是LCS算法

（見這裏的例子：http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf在最後一頁）

我的問題是這樣的：考慮運行這兩個字符串以下輸出矩陣：通過LCS「abfcytyruc」和「vxczcxabfc」：

- 0 0 0 0 0 0 0 0 0 0 0 
- 0 0 0 0 0 0 0 1 1 1 1 
- 0 0 0 0 0 0 0 1 2 2 2 
- 0 0 0 0 0 0 0 1 2 3 3 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 2 2 2 2 3 4

這是真的，我們可以找到公共子序列的基礎上，僅在矩陣的最後一列，而不需要一些更多的空間複雜度？

來源

2013-11-22 so.very.tired

當使用簡單的動態規劃方法（如上面），你只能確定與最後一列的LCS的長度，但不是實際的序列。

這裏它失敗的例子：

a a a a a c b b 
c 0 0 0 0 0 1 1 1 
b 0 0 0 0 0 1 2 2 
b 0 0 0 0 0 1 2 3 
a 1 1 1 1 1 1 2 3 
a 1 2 2 2 2 2 2 3 
a 1 2 3 3 3 3 3 3 
a 1 2 3 4 4 4 4 4

看一看的海森堡算法。它是Needleman-Wunsch算法的分而治之改編，適用於線性空間。

如需進一步閱讀：http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/05/Hirschberg75.pdf

來源

2013-11-22 20:50:38 cytofu

感謝您的鏈接。雖然一個問題... 爲什麼是不是真的，對於在最後一列每X_I（或最後一排，順便說一句）;如果X_I和X_I + 1是不同的，則X_I + 1實際上表示在輸入字符串中的字符，屬於公共子序列的索引。 –

在小例子中構造失敗的東西並不那麼容易。我在答案中加了1。 – cytofu

決定什麼是LCS算法

回答

相關問題