Red Huang

計算 LCS 的長度

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

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

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

5. // DP 的表格

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

7. void LCS()

8. {

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

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

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

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

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

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

15.             else

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

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

18. }

找出一個 LCS

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

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

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

5. // DP 的表格

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

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

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

9. void LCS()

10. {

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

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

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

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

15.             {

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

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

18.                 prev [i][j] = 左上方；

19.             }

20.             else

21.             {

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

23.                 {

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

25.                     prev [i][j] = 左方；

26.                 }

27.                 else

28.                 {

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

30.                     prev [i][j] = 上方；

31.                 }

32.             }

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

34.     cout << "LCS 為 ";

35.     print_LCS(s1_length, s2_length);

36. }

37. void print_LCS(int i, int j)

38. {

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

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

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

42.     {

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

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

45.     }

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

47.         print_LCS(i-1, j);

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

49.         print_LCS(i, j-1);

50. }