目錄
最長公共子序列簡介舉例說明并分析代碼塊測試結果
最長公共子序列簡介
一個給定序列的子序列是在該序列中刪去若干元素后得到的序列，確切的說，若給定序列X={x0,x1…,xm-1}, 則另一序列Z={z0,z1,…,zk-1},X的子序列是指存在一個嚴格的下標序列{i0,i1…,ik-1},使得對于所有的j=0，1，…，k-1有Zj=Xij。例如序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相應的遞增下標序列維{1，2，4，6}。
最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。求解最長公共子序列長度。
舉例說明并分析
窮舉搜索法是最容易想到的方法，對X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中記錄最長的公共子序列，X的所有子序列都檢查后即可求出X和Y的最長公共子序列，x的每個子序列相應與下標集{0，1，2，……，m-1}的一個子集，因此共有2的m次方個不同子序列，從而窮舉法需要指數時間。 事實上，最長公共子序列問題具有最優子結構性質。
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。
這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。
首先建立子問題最優值的遞歸關系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度，b[i][j]記錄c[i][j]的值是由哪一個子問題的解得到的。 動態規劃是自底向上進行遞歸的 那么在計算c[i][j]之前，c[i-1][j-1]和c[i-1][j]以及c[i][j-1]都應該知道
代碼塊
#include <stdio.h>#include<stdlib.h>#include <string.h>#define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]){ int i, j; for (i = 0; i <= m; i++) c[i][0] = 0; //單個序列的最長公共子序列為0 for (j = 1; j <= n; j++) c[0][j] = 0; //單個序列的最長公共子序列為0 for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i-1] == y[j-1])//因為x序列和y序列的坐標都是從0開始的，所有最后一個下標為i-1,j-1; { c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 1; } else if (c[i - 1][j] >= c[i][j - 1]) { c[i][j] = c[i - 1][j]; //滿足m-1!=n-1且k-1！=m-1情況從X{0,1,2...,m-2}和Y{0,1,2..,n-1}開始尋找 b[i][j] = 2; } else { c[i][j] = c[i][j - 1]; //滿足m-1!=n-1且k-1！=n-1情況從X{0,1,2...,m-1}和Y{0,1,2..,n-2}開始尋找 b[i][j] = 3; } } }}void PRintLCS(int b[][MAXLEN], char *x, int i, int j){ if (i == 0 || j == 0) //遞歸到兩個數組中任意一個的下標為0時結束 return; if (b[i][j] == 1) { PrintLCS(b, x, i - 1, j - 1); printf("%c ", x[i - 1]); } else if (b[i][j] == 2) PrintLCS(b, x, i - 1, j); else PrintLCS(b, x, i, j - 1);}int main(int argc, char **argv){ char x[MAXLEN] ; char y[MAXLEN] ; printf("請輸入較長序列的數據:/n"); scanf("%s", x); getchar(); printf("請輸入較短序列的數據:/n"); scanf("%s", y); int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); printf("最長公共子序列是:/n"); PrintLCS(b, x, m, n);//x數組必須是序列較長的數組 printf("/n長度是%d", c[m][n]); system("pause"); return 0;}
測試結果
