問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2250思路:
以單詞為單位的LCS，另外需要記錄路徑信息
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_NUM 101
5 #define MAX_LEN 31
6 char first[MAX_NUM][MAX_LEN];
7 char second[MAX_NUM][MAX_LEN];
8 int fcnt, scnt;
9 int table[MAX_NUM][MAX_NUM];
10 char path[MAX_NUM][MAX_NUM];
11
12 void
13 output(int i, int j)
14 {
15 if(i==0 || j==0)
16 return;
17 if(path[i][j] == 'u')
18 output(i-1, j);
19 else if(path[i][j] == 'l')
20 output(i, j-1);
21 else {
22 output(i-1, j-1);
23 printf("%s ", first[i-1]);
24 }
25 }
26
27 void
28 lcs()
29 {
30 int i, j;
31 for(i=0; i<=fcnt; i++)
32 table[i][0] = 0;
33 for(j=0; j<=scnt; j++)
34 table[0][j] = 0;
35 for(i=1; i<=fcnt; i++) {
36 for(j=1; j<=scnt; j++) {
37 if(strcmp(first[i-1], second[j-1]) == 0) {
38 table[i][j] = table[i-1][j-1] + 1;
39 path[i][j] = 'y';
40 } else if(table[i-1][j] > table[i][j-1]) {
41 table[i][j] = table[i-1][j];
42 path[i][j] = 'u';
43 } else {
44 table[i][j] = table[i][j-1];
45 path[i][j] = 'l';
46 }
47 }
48 }
49 }
50
51 int
52 main(int argc, char **argv)
53 {
54 while(1) {
55 fcnt = scnt = 0;
56 memset(table, 0, sizeof(table));
57 memset(path, 0, sizeof(path));
58 if(scanf("%s", first[fcnt++]) == EOF)
59 break;
60 while(scanf("%s", first[fcnt]) && first[fcnt][0]!='#')
61 ++fcnt;
62 while(scanf("%s", second[scnt]) && second[scnt][0]!='#')
63 ++scnt;
64 lcs();
65 output(fcnt, scnt);
66 printf("\n");
67 }
68 }