Lightoj 1110 - An Easy LCS

http://lightoj.com/volume_showproblem.php?problem=1110

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define For(i,a) for(int i=0;i<a;++i)
4. #define foreach(x,v) for(typeof (v).begin() x = (v).begin(); x!= (v).end(); x++)
5. #define all(x) x.begin(),x.end()
6. #define rall(x) x.rbegin(),x.rend()
7. #define D(x) cout<< #x " = "<<(x)<<endl
8. #define Dbg if(1)
9. #define MAXNODES 1000
10.  
11. int dp[101][101];
12. string lex[101][101];
13.  
14. int lcs(const string &a,const string &b, string &ans){
15.   int n=a.size(),m=b.size();
16.   if(n==0 || m==0) return 0;
17.   for(int i=0;i<=n;++i){
18.     dp[i][0] = 0;
19.     lex[i][0].clear();
20.   }
21.   for(int j=0;j<=m;++j){
22.     dp[0][j] = 0;
23.     lex[0][j].clear();
24.   }
25.   for(int i=1;i<=n;i++){
26.     for(int j=1;j<=m;++j){
27.       if(a[i-1]==b[j-1]){
28.         dp[i][j] = dp[i-1][j-1]+1;
29.         lex[i][j] = lex[i-1][j-1] + a[i-1];
30.       }
31.       else if(dp[i][j-1] > dp[i-1][j]){
32.         dp[i][j] = dp[i][j-1];
33.         lex[i][j] = lex[i][j-1];
34.       }else if(dp[i][j-1] < dp[i-1][j]){
35.         dp[i][j] = dp[i-1][j];
36.         lex[i][j] = lex[i-1][j];
37.       }else{
38.         dp[i][j] = dp[i-1][j];
39.         lex[i][j] = min(lex[i-1][j],lex[i][j-1]);
40.       }
41.     }
42.   }
43.  
44.   ans=lex[n][m];
45.  
46.   return dp[n][m];
47. }
48.  
49. int main(){
50.   int numcas;cin>>numcas;
51.   for(int cid=1;cid<=numcas;++cid){
52.     string a,b;cin>>a>>b;
53.     string ans;
54.     cout<<"Case "<<cid<<": "<<((lcs(a,b,ans)==0)?":(":ans)<<endl;
55.   }
56.   return 0;
57. }

1. /*
2. // another implementation
3. #include <bits/stdc++.h>
4. using namespace std;
5. #define N 100
6. int L[N][N];
7.  set<string> findLCS(string X, string Y, int m, int n){
8.     set<string> s;
9.     if (m == 0 || n == 0){
10.         s.insert("");
11.         return s;
12.     }
13.  
14.     if (X[m - 1] == Y[n - 1]){
15.         set<string> tmp = findLCS(X, Y, m - 1, n - 1);
16.     for (string str : tmp)
17.             s.insert(str + X[m - 1]);
18.     }
19.     else{
20.         if (L[m - 1][n] >= L[m][n - 1])
21.             s = findLCS(X, Y, m - 1, n);
22.     if (L[m][n - 1] >= L[m - 1][n]){
23.             set<string> tmp = findLCS(X, Y, m, n - 1);
24.         s.insert(tmp.begin(), tmp.end());
25.         }
26.     }
27.     return s;
28. }
29.  
30. int LCS(string X, string Y, int m, int n){
31.     for (int i = 0; i <= m; i++){
32.         for (int j = 0; j <= n; j++){
33.             if (i == 0 || j == 0)
34.                 L[i][j] = 0;
35.             else if (X[i - 1] == Y[j - 1])
36.                 L[i][j] = L[i - 1][j - 1] + 1;
37.             else
38.                 L[i][j] = max(L[i - 1][j], L[i][j - 1]);
39.         }
40.     }
41.     return L[m][n];
42. }
43.  
44. int main(){
45.     int ts;
46.     cin>>ts;
47.     for(int k = 1; k <= ts; k++){
48.     string X;
49.     string Y;
50.     cin>>X>>Y;
51.     int m = X.length();
52.     int n = Y.length();
53.     //cout << "LCS length is " << LCS(X, Y, m, n) << endl;
54.     set<string> s = findLCS(X, Y, m, n);
55.     set<string> :: iterator p;
56.     p = s.begin();
57.     if((*p) == "") printf("Case %d: :(\n", k);
58.     else printf("Case %d: %s\n", k, (*p).c_str());
59.     s.clear();
60.     }
61.     return 0;
62. }
63.  
64. */

1.