Longest Common Subsequence(LCS)

    這次要介紹的是Longest Common Subsequence，以下舉個例子來說，給予兩個字串“ABCDGH”和“AEDFHR”他們的共同最長子序列即是“ADH”長度為3，註：子序列是以相同的相對順序出現的序列，但不一定是連續的。例如，“abc”，“abg”，“bdf”，“aeg”，“”acefg“等等是”abcdefg“的子序列。

演算法(運用遞迴解法)：

1. 讓兩個input字串為X[0....m-1]和Y[0....n-1]，並且長度分別為m和n，LCS(X[0....m-1], Y[0....n-1])為這兩字串的LCS長度。
2. 從最後一個字元開始比較，如果一樣則為1+ LCS(X[0....m-2], Y[0....n-2])，否則的話為MAX( LCS(X[0....m-2], Y[0....n-1]), LCS(X[0....m-1], Y[0....n-2]))即找出扣掉X最後一字元與Y或是扣掉Y的最後一個字元與X的LCS長度。

C程式碼 :

#include <stdio.h>
#include <string.h>

//宣告max function
int max(int a, int b); 

//LCS function
int lcs(char* a, char* b, int m, int n){

     if( m == 0 || n ==0){
          return 0;
     }

     

     //開始遞迴解法(以上演算法的第二步驟)

     if(a[m-1] == b[n-1])
          return 1 + lcs(a, b, m-1, n-1);
     else
          return max(lcs(a, b, m-1, n), lcs(a, b, m, n-1));
     }


     int max(int c, int d){
          return (c > d)? c: d;
     }


int main() {

     char X[80];
     char Y[80];

     scanf("%s %s", X, Y);
     int m = strlen(X);
     int n = strlen(Y);

     printf("Length of LCS is %d", lcs( X, Y, m, n ) );

     return 0;

}


**番外篇：其實若用遞回樹將MAX( LCS(X[0....m-2], Y[0....n-1]), LCS(X[0....m-1], Y[0....n-2]))展開會發現其實有很多重複計算到的遞迴式，故另外一種方法我們可以使用Dynamic Programming來解。