最長公共子序列優化

我目前正在嘗試查找和打印2個給定字符串的最長公共子序列。我使用最常用的算法，無需遞歸。如果我保留整個數組，這很簡單，但我想優化一下，只使用2行，你可以在下面的代碼中看到。隨着這一變化，找到長度仍然簡單，工作正常，但恢復子序列不再那麼容易。我試圖用幾種方法做，但都沒有成功。下面你可以看到我的最後一次嘗試。雖然它適用於相同的情況，但也有失敗的情況。經過很長時間的思考，我開始相信，沒有辦法使用只有2行的數組恢復子序列。我的研究沒有給我確切的答案，所以我問是否有辦法實現我想要做的事情？或者我堅持保持整個陣列，如果我想打印？最長公共子序列優化

//finding length of longest common subsequence 
for(int i=1; i<m; i++) { 
    for(int j=1; j<n; j++) { 
     if(sequece1[i-1] == sequence2[j-1]) { 
      tab[i%2][j] = tab[(i-1)%2][j-1] + 1; 
     } else { 
      tab[i%2][j] = max(tab[i%2][j-1],tab[(i-1)%2][j]); 
     } 
    } 
} 

//trying to reconstruct longest common subsequence 
int last_row = (m-1)%2; 
for(int j=n-1; j>0; j--) { 
    if(tab[last_row][j-1] < tab[last_row][j]) { 
     if(last_row == 0) { 
      common_part += sequence2[j]; 
      } else { 
      common_part += sequence2[j-1]; 
     } 
    } 
}

來源

2015-04-22 Dcortez

[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem）這會幫助你。 –

似乎沒有簡單的方法來完成，因爲如果只保留最後兩列，信息的重要部分就會丟失。

例如，考慮兩種情況：（abcc，acc）字符串和（abcc,bcc）字符串。對於這些情況的矩陣將是

1 1 1 1 and 0 1 1 1 
1 1 2 2   0 1 2 2 
1 1 2 3   0 1 2 3

你看到最後兩列是在兩種情況下是相同的，所以你不會區分這些情況下，只有通過最後兩列判斷。但是你需要區分它們，因爲答案是不同的（acc和bcc）。當然，你仍然有原始字符串，並且可以使用來自那裏的信息，但我認爲（儘管我沒有證明這一點），這或多或少地相當於爲原始字符串的某些前綴找到LCS。

與此同時，有a more advanced algorith在二次時間和線性空間工作。

來源

2015-04-22 18:17:27 Petr

儘管我正在使用行，並且在您的示例「acc」和「bcc」中有不同的最後2行，但我知道有些情況下它們會相同。 Hitschberg算法會做，但我想我會留在整個桌子。感謝幫助！ – Dcortez

最長公共子序列優化

回答

相關問題