问题描述：给出两个字符串X， Y，求一个串同时是X， Y的子串并且是所有满足条件里的最长的串。
分析：题目是一个动态规划问题。设c[i][j]表示 x = {x0, x1, x2, .. xi-1}和 y = {y0, y1, y2, .... yj-1},的最长子序列长度， x， y的字串为 z= {z0, z1, z2, ... zk}。所以有一下规律：
当x[i-1] = y[j-1]时，z[k] = x[i-1] = y[j - 1], c[i][j] = c[i-1][j-1] + 1;
当x[i-1] != y[j-1] 且 z[k] != x[i-1], c[i][j] = c[i-1][j]
当x[i-1] != y[j-1] 且 z[k] != y[i-1], c[i][j] = c[i][j-1]
所以:
c[i][j] = c[i-1][j-1] (x[i-1] == y[i-1])
c[i][j] = max(c[i-1][j], c[i][j-1]) (x[i-1] != y[i-1])
这里只是求出了最长公共子序列的长度。至于完整序列可以用一下方法：
设dir[i][j] 表示(i-1, j-1)处的最长公共序列的来路（就是通过哪个过程来的）
比如：当x[i-1] = y[j-1]时，c[i][j] = c[i-1][j-1] + 1; 说明c[i][j]是从c[i-1][j-1] 方向来的。所以用dir[i][j]做一个标记（比如记为0）
当x[i-1] != y[j-1] 且 z[k] != x[i-1], c[i][j] = c[i-1][j] 时记dir[i][j] = 1
当x[i-1] != y[j-1] 且 z[k] != y[i-1], c[i][j] = c[i][j-1] 时记dir[i][j] = -1;
具体过整如图：
ps：前文都是看了一些资料，按照自己的理解写得一点总结。如有错误，欢迎指正。
代码实现：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1000;
char x[N], y[N];
int c[N][N], d[N][N];
int LCS_l(int n, int m) {
int i, j;
for(i = 0; i <= n; i++) c[i][0] = 0;
for(j = 0; j <= m; j++) c[0][j] = 0;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(x[i-1] == y[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
d[i][j] = 0;
} else if(c[i][j-1] >= c[i-1][j]) {
c[i][j] = c[i][j-1];
d[i][j] = 1;
} else {
c[i][j] = c[i-1][j];
d[i][j] = -1;
}
}
}
return c[n][m];
}
void LCS_p(int i, int j) {
if(i == 0 || j == 0) return ;
if(d[i][j] == 0) {
LCS_p(i-1, j-1);
printf("%c %c\n", x[i-1], y[j-1]);
} else if(d[i][j] == 1) {
LCS_p(i, j-1);
} else {
LCS_p(i-1, j);
}
}
int main() {
//freopen("data.in", "r", stdin);
int t, n, m;
while(~scanf("%d", &t)) {
while(t--) {
scanf("%d", &n); getchar();
scanf("%s", x);
scanf("%d", &m); getchar();
scanf("%s", y);
memset(c, 0, sizeof(c));
cout << LCS_l(n, m) << endl;
LCS_p(n, m);
}
}
return 0;
}
练习题目：Human Gene Functions：
http://acm.hdu.edu.cn/showproblem.php?pid=1080
题解:思路就是最长上升子序列，不过稍微变化了一下。
My Code:
View Code
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4
5 using namespace std;
6
7 const int N = 1000;
8
9 char x[N], y[N];
10 int c[N][N];
11 int map[5][5] = {
12 {5, -1, -2, -1, -3},
13 {-1, 5, -3, -2, -4},
14 {-2, -3, 5, -2, -2},
15 {-1, -2, -2, 5, -1},
16 {-3, -4, -2, -1, 0},
17 };
18
19 int p(char x) {
20 if(x == 'A') return 0;
21 else if(x == 'C') return 1;
22 else if(x == 'G') return 2;
23 else if(x == 'T') return 3;
24 else return 4;
25 }
26
27
28 int LCS_l(int n, int m) {
29 int i, j;
30
31 for(i = 1; i <= n; i++) c[i][0] = c[i-1][0] + map[p(x[i-1])][4];
32 for(i = 1; i <= m; i++) c[0][i] = c[0][i-1] + map[4][p(y[i-1])];
33
34 for(i = 1; i <= n; i++) {
35 for(j = 1; j <= m; j++) {
36 c[i][j] = max(c[i-1][j-1] + map[p(x[i-1])][p(y[j-1])],
37 max(c[i][j-1] + map[4][p(y[j-1])], c[i-1][j] + map[p(x[i-1])][4]));
38 //printf("%d %d %d\n", i, j, c[i][j]);
39 }
40 }
41 return c[n][m];
42 }
43
44 /*void LCS_p(int i, int j) {
45 if(i == 0 || j == 0) return ;
46 if(d[i][j] == 0) {
47 LCS_p(i-1, j-1);
48 printf("%c %c\n", x[i-1], y[j-1]);
49 } else if(d[i][j] == 1) {
50 LCS_p(i, j-1);
51 } else {
52 LCS_p(i-1, j);
53 }
54 }*/
55
56 int main() {
57 //freopen("data.in", "r", stdin);
58
59 int t, n, m;
60 while(~scanf("%d", &t)) {
61 while(t--) {
62 scanf("%d", &n); getchar();
63 scanf("%s", x);
64 scanf("%d", &m); getchar();
65 scanf("%s", y);
66 //puts(x); puts(y);
67 memset(c, 0, sizeof(c));
68 cout << LCS_l(n, m) << endl;
69 }
70 }
71 return 0;
72 }