Longest Common Subsequence

計算 LCS 的長度

1. // 為了實作方便，從陣列的第1格開始存入序列。


2. int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};


3. int s2[5+1] = {0, 3, 5, 3, 2, 8};


4. // DP 的表格


5. int array[7+1][5+1];


6. void LCS()


7. {


8.     將 array[x][0] 和 array[0][x] 都設為 0 ;


9.     for (int i = 1; i <= s1_length; i++)


10.         for (int j = 1; j <= s2_length; j++)


11.             if (s1[i] == s2[j])


12.                 // 這裡加上的 1 是指 e1 的長度為 1


13.                 array[i][j] = array[i-1][j-1] + 1;


14.             else


15.                 array[i][j] = max(array[i-1][j], array[i][j-1]);


16.     cout << "LCS 的長度是" << array[seq1_length][seq2_length];


17. }

找出一個 LCS

1. // 為了實作方便，從陣列的第1格開始存入序列。


2. int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};


3. int s2[5+1] = {0, 3, 5, 3, 2, 8};




5. // DP 的表格


6. int array[7+1][5+1];




8. // 記錄這一格的最大值是從哪一格求得的


9. int prev[7+1][5+1];




11. void LCS()


12. {


13.     將 array[x][0] 和 array[0][x] 都設為 0 ;




15.     for (int i = 1; i <= s1_length; i++)


16.         for (int j = 1; j <= s2_length; j++)


17.             if (s1[i] == s2[j])


18.             {


19.                 // 這裡加上的 1 是指 e1 的長度為 1


20.                 array[i][j] = array[i-1][j-1] + 1;


21.                 prev[i][j] = 左上方;


22.             }


23.             else


24.             {


25.                 if (array[i-1][j] < array[i][j-1])


26.                 {


27.                     array[i][j] = array[i][j-1];


28.                     prev[i][j] = 左方;


29.                 }


30.                 else


31.                 {


32.                     array[i][j] = array[i-1][j];


33.                     prev[i][j] = 上方;


34.                 }


35.             }




37.     cout << "LCS 的長度是" << array[s1_length][s2_length];




39.     cout << "LCS 為 ";


40.     print_LCS(s1_length, s2_length);


41. }




43. void print_LCS(int i, int j)


44. {


45.     // 第一個或第二個 sequence 為空的的時候就可停止了


46.     if (i==0 || j==0) return;




48.     if (prev[i][j] == 左上方)


49.     {


50.         print_LCS(i-1, j-1);


51.         cout << s1[i];  // 印出 LCS 的元素


52.     }


53.     else if (prev[i][j] == 上方)


54.         print_LCS(i-1, j);


55.     else if (prev[i][j] == 左方)


56.         print_LCS(i, j-1);


57. }