題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續出現在字符串二中。請編寫一個函數，輸入兩個字符串，求它們的最長公共子序列，并打印出最長公共子序列。
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子序列，則輸出它們的長度4，并打印任意一個子序列。
分析：求最長公共子序列（Longest Common Subsequence, LCS）是一道非常經典的動態規劃題，因此一些重視算法的公司像MicroStrategy都把它當作面試題。
完整介紹動態規劃將需要很長的篇幅，因此我不打算在此全面討論動態規劃相關的概念，只集中對LCS直接相關內容作討論。如果對動態規劃不是很熟悉，請參考相關算法書比如算法討論。
考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質：
（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[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長度，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的，以決定輸出最長公共字串時搜索的方向。
我們是自底向上進行遞推計算，那么在計算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計算出來。此時我們根據X[i] == Y[j]還是X[i] != Y[j]，就可以計算出c[i][j]。
問題的遞歸式寫成：
回溯輸出最長公共子序列過程：
算法分析：
由于每次調用至少向上或向左（或向上向左同時）移動一步，故最多調用(m + n)次就會遇到i = 0或j = 0的情況，此時開始返回。返回時與遞歸調用時方向相反，步數相同，故算法時間復雜度為Θ(m + n)。
完整的實現代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
/** 找出兩個字符串的最長公共子序列的長度 ** author :liuzhiwei ** data :2011-08-15 **/#include "stdio.h" #include "string.h" #include "stdlib.h" int LCSLength(char* str1, char* str2, int **b) { int i,j,length1,length2,len; length1 = strlen(str1); length2 = strlen(str2); //雙指針的方法申請動態二維數組 int **c = new int*[length1+1]; //共有length1+1行 for(i = 0; i < length1+1; i++) c[i] = new int[length2+1]; //共有length2+1列 for(i = 0; i < length1+1; i++) c[i][0]=0; //第0列都初始化為0 for(j = 0; j < length2+1; j++) c[0][j]=0; //第0行都初始化為0 for(i = 1; i < length1+1; i++) { for(j = 1; j < length2+1; j++) { if(str1[i-1]==str2[j-1]) //由于c[][]的0行0列沒有使用，c[][]的第i行元素對應str1的第i-1個元素 { c[i][j]=c[i-1][j-1]+1; b[i][j]=0; //輸出公共子串時的搜索方向 } else if(c[i-1][j]>c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=1; } else { c[i][j]=c[i][j-1]; b[i][j]=-1; } } } /* for(i= 0; i < length1+1; i++) { for(j = 0; j < length2+1; j++) printf("%d ",c[i][j]); printf("\n"); } */ len=c[length1][length2]; for(i = 0; i < length1+1; i++) //釋放動態申請的二維數組 delete[] c[i]; delete[] c; return len; } void PrintLCS(int **b, char *str1, int i, int j) { if(i==0 || j==0) return ; if(b[i][j]==0) { PrintLCS(b, str1, i-1, j-1); //從后面開始遞歸，所以要先遞歸到子串的前面，然后從前往后開始輸出子串 printf("%c",str1[i-1]); //c[][]的第i行元素對應str1的第i-1個元素 } else if(b[i][j]==1) PrintLCS(b, str1, i-1, j); else PrintLCS(b, str1, i, j-1); } int main(void) { char str1[100],str2[100]; int i,length1,length2,len; printf("請輸入第一個字符串："); gets(str1); printf("請輸入第二個字符串："); gets(str2); length1 = strlen(str1); length2 = strlen(str2); //雙指針的方法申請動態二維數組 int **b = new int*[length1+1]; for(i= 0; i < length1+1; i++) b[i] = new int[length2+1]; len=LCSLength(str1,str2,b); printf("最長公共子序列的長度為：%d\n",len); printf("最長公共子序列為："); PrintLCS(b,str1,length1,length2); printf("\n"); for(i = 0; i < length1+1; i++) //釋放動態申請的二維數組 delete[] b[i]; delete[] b; system("pause"); return 0; } |
程序的效果圖如下：
第二種方法為：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
/** 找出兩個字符串的最長公共子序列的長度 ** author :liuzhiwei ** data :2011-08-15 **/#include "stdio.h" #include "string.h" #include "stdlib.h" int LCSLength(char* str1, char* str2) //求得兩個字符串的最大公共子串長度并輸出公共子串 { int i,j,length1,length2; length1 = strlen(str1); length2 = strlen(str2); //雙指針的方法申請動態二維數組 int **c = new int*[length1+1]; //共有length1+1行 for(i = 0; i < length1+1; i++) c[i] = new int[length2+1]; //共有length2+1列 for(i = 0; i < length1+1; i++) c[i][0]=0; //第0列都初始化為0 for(j = 0; j < length2+1; j++) c[0][j]=0; //第0行都初始化為0 for(i = 1; i < length1+1; i++) { for(j = 1; j < length2+1; j++) { if(str1[i-1]==str2[j-1]) //由于c[][]的0行0列沒有使用，c[][]的第i行元素對應str1的第i-1個元素 c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>c[i][j-1]) c[i][j]=c[i-1][j]; else c[i][j]=c[i][j-1]; } } //輸出公共子串 char s[100]; int len,k; len=k=c[length1][length2]; s[k--]='\0'; i=length1,j=length2; while(i>0 && j>0) { if(str1[i-1]==str2[j-1]) { s[k--]=str1[i-1]; i--; j--; } else if(c[i-1][j]<c[i][j-1]) j--; else i--; } printf("最長公共子串為："); puts(s); for(i = 0; i < length1+1; i++) //釋放動態申請的二維數組 delete[] c[i]; delete[] c; return len; } int main(void) { char str1[100],str2[100]; int length1,length2,len; printf("請輸入第一個字符串："); gets(str1); printf("請輸入第二個字符串："); gets(str2); length1 = strlen(str1); length2 = strlen(str2); len=LCSLength(str1,str2); printf("最長公共子串的長度為：%d\n",len); system("pause"); return 0; } |
問題拓展：設A、B、C是三個長為n的字符串，它們取自同一常數大小的字母表。設計一個找出三個串的最長公共子序列的O(n^3)的時間算法。
思路：跟上面的求2個字符串的公共子序列是一樣的思路，只不過這里需要動態申請一個三維的數組，三個字符串的尾字符不同的時候，考慮的情況多一些而已。
思路：跟上面的求2個字符串的公共子序列是一樣的思路，只不過這里需要動態申請一個三維的數組，三個字符串的尾字符不同的時候，考慮的情況多一些而已。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/** 找出三個字符串的最長公共子序列的長度 ** author :liuzhiwei ** data :2011-08-15 **/#include "stdio.h" #include "string.h" #include "stdlib.h" int max1(int m,int n) { if(m>n) return m; else return n; } int max2(int x,int y,int z,int k,int m,int n) { int max=-1; if(x>max) max=x; if(y>max) max=y; if(z>max) max=z; if(k>max) max=k; if(m>max) max=m; if(n>max) max=n; return max; } int LCSLength(char* str1, char* str2, char* str3) //求得三個字符串的最大公共子序列長度并輸出公共子序列 { int i,j,k,length1,length2,length3,len; length1 = strlen(str1); length2 = strlen(str2); length3 = strlen(str3); //申請動態三維數組 int ***c = new int**[length1+1]; //共有length1+1行 for(i = 0; i < length1+1; i++) { c[i] = new int*[length2+1]; //共有length2+1列 for(j = 0; j<length2+1; j++) c[i][j] = new int[length3+1]; } for(i = 0; i < length1+1; i++) { for(j = 0; j < length2+1; j++) c[i][j][0]=0; } for(i = 0; i < length2+1; i++) { for(j = 0; j < length3+1; j++) c[0][i][j]=0; } for(i = 0; i < length1+1; i++) { for(j = 0; j < length3+1; j++) c[i][0][j]=0; } for(i = 1; i < length1+1; i++) { for(j = 1; j < length2+1; j++) { for(k = 1; k < length3+1; k++) { if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1]) c[i][j][k]=c[i-1][j-1][k-1]+1; else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1]) c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]); else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1]) c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]); else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1]) c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]); else { c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]); } } } } len=c[length1][length2][length3]; for(i = 1; i < length1+1; i++) //釋放動態申請的三維數組 { for(j = 1; j < length2+1; j++) delete[] c[i][j]; delete[] c[i]; } delete[] c; return len; } int main(void) { char str1[100],str2[100],str3[100]; int len; printf("請輸入第一個字符串："); gets(str1); printf("請輸入第二個字符串："); gets(str2); printf("請輸入第三個字符串："); gets(str3); len=LCSLength(str1,str2,str3); printf("最長公共子序列的長度為：%d\n",len); system("pause"); return 0; } |
程序的效果圖如下：
