LCS问题，不同的是要打印LCS；
算法导论上的方法，f 可以使用滚动数组， 应该有更好的打印方法；
要注意格式：PE了一次，就是因为最后一个单词后面不能留空格。
1 # include <stdio.h>
2 # include <string.h>
3
4 # define MAX(x, y) ((x)>(y) ? (x):(y))
5
6 # define UPL 1
7 # define UP 2
8 # define LEFT 3
9
10 int len[2];
11 char s1[101][31];
12 char s2[101][31];
13 int f[101][101];
14 short d[101][101];
15
16 void print_lcs(int row, int col, int *cnt);
17
18 int main()
19 {
20 int i, j;
21 int *cnt;
22
23 while (~scanf("%s", s1[1]))
24 {
25 i = 1; while (0 != strcmp(s1[i], "#") && scanf("%s", s1[++i])) ; len[0] = i-1;
26 i = 0; while (scanf("%s", s2[++i]) && 0 != strcmp(s2[i], "#")) ; len[1] = i-1;
27
28 memset(f, 0, sizeof(f));
29
30 for ( i = 1; i <= len[0]; ++i)
31 for ( j = 1; j <= len[1]; ++j)
32 if (0 == strcmp(s1[i], s2[j]))
33 {
34 f[i][j] = f[i-1][j-1] + 1;
35 d[i][j] = UPL;
36 }
37 else if (f[i-1][j] > f[i][j-1])
38 {
39 f[i][j] = f[i-1][j];
40 d[i][j] = UP;
41 }
42 else
43 {
44 f[i][j] = f[i][j-1];
45 d[i][j] = LEFT;
46 }
47
48 cnt = &f[len[0]][len[1]];
49 print_lcs(len[0], len[1], cnt);
50 }
51
52 return 0;
53 }
54
55 void print_lcs(int row, int col, int *cnt)
56 {
57 if (!row || !col) return;
58 if (d[row][col] == UPL)
59 {
60 print_lcs(row-1, col-1, cnt);
61 --(*cnt);
62 printf("%s", s1[row]);
63 if (*cnt != 0) putchar(' ');
64 else putchar('\n');
65 }
66 else if (d[row][col] == LEFT)
67 {
68 print_lcs(row, col-1, cnt);
69 }
70 else print_lcs(row-1, col, cnt);
71 }