TOJ 1139.Compromise，toj1139.compromise

TOJ 1139.Compromise，toj1139.compromise

2015-06-03

問題簡述：

　　大概就是輸入兩段文本（用小寫英文字母表示），分別用#表示一段話的結束輸入，輸出這兩個文本的最長公共子序列。

　　簡單的LCS問題，但是輸入的是一段話了，而且公共部分比較是字符串的比較。

　　原題鏈接：http://acm.tju.edu.cn/toj/showp.php?pid=1139

解題思路：

　　簡單的最長公共子序列問題，只不過過程中比較的是兩個字符串，故使用二維字符數組保存輸入文本。

　　輸入 x[1...m][], y[1...n][] ,c[i,j]代表兩個文本的LCS的長度，遞歸方程如下：

　　c[0,j] = c[i,0] = 0;

　　c[i,j] = c[i-1,j-1] + 1               if x[i]==y[j]

　　c[i,j] = max(c[i-1,j], c[i,j-1])    if x[i]!=y[j]

　　　　使用 b[i,j] 表示三種情況（=1,=2,=3），方便以後輸出LCS：

　　　　if b[i,j] == 1,表示 x[i] == y[j], 可以輸出;

　　　　if b[i,j] == 2,表示 c[i-1,j] > c[i,j-1], i--即可;

　　　　if b[i,j] == 3,表示 c[i,j-1] > c[i-1,j], j--即可;

源代碼：

 1 /*
 2 OJ: TOJ
 3 ID: 3013216109
 4 TASK: 1139.Compromise
 5 LANG: C++
 6 NOTE: LCS(DP)
 7 */
 8 #include <iostream>
 9 #include <cstring>
10 using namespace std;
11 
12 int main()
13 {
14     char x[105][31],y[105][31],ans[105][31];
15     int c[105][105],b[105][105];
16     int i,j,k,m,n;
17     while(cin >> x[1]) {
18         for(i=2;;i++) {
19             cin >> x[i];
20             if(x[i][0]=='#')break;
21         }
22         for(j=1;;j++) {
23             cin >> y[j];
24             if(y[j][0]=='#')break;
25         }
26         m=i-1; n=j-1;
27         for(i=0;i<=m;i++)
28             c[i][0]=0;
29         for(i=1;i<=n;i++)
30             c[0][i]=0;
31         for(i=1;i<=m;i++) {
32             for(j=1;j<=n;j++) {
33                 if(!strcmp(x[i],y[j])) {
34                     c[i][j]=c[i-1][j-1]+1;
35                     b[i][j]=1;
36                 }
37                 else if(c[i-1][j]>=c[i][j-1]) {
38                     c[i][j]=c[i-1][j];
39                     b[i][j]=2;
40                 }
41                 else {
42                     c[i][j]=c[i][j-1];
43                     b[i][j]=3;
44                 }
45             }
46         }
47         i=m;j=n;
48         k=c[m][n]-1;
49         while(i>0&&j>0&&k>=0) {
50             if(b[i][j]==1) {
51                 strcpy(ans[k],x[i]);
52                 i--;j--;k--;
53             }
54             else if(b[i][j]==2) i--;
55             else if(b[i][j]==3) j--;
56             else break;
57         }
58         for(i=0;i<c[m][n]-1;i++)
59             cout << ans[i] <<" ";
60         cout <<ans[c[m][n]-1]<<endl;
61     }
62     return 0;
63 }