Friday 28 July 2017

Lightoj 1110 - An Easy LCS

  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.  

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...