Facebook
From Diminutive Pig, 2 Weeks ago, written in C++.
Embed
Download Paste or View Raw
Hits: 35
  1. #include<iostream>
  2. #include<fstream>
  3. #include<vector>
  4. #include<queue>
  5. #include<string>
  6. #include<math.h>
  7. using namespace std;
  8. #define BIT_TOOGLE(num, index) (num) |= (1<<(index))
  9. #define BIT_CLEAR(num, index) (num) &= ~(1<<(index))
  10.  
  11. #define BIT_SET_VALUE(num, index, bit) \
  12. if(bit)\
  13.         BIT_TOOGLE(num,index);\
  14. else\
  15.         BIT_CLEAR(num,index);
  16. bool bit_check(uint8_t num, uint8_t index){
  17.         uint8_t mask=pow(2,index);
  18.         mask&=num;
  19.         if(mask==pow(2,index))
  20.         return true;
  21.         else
  22.         return false;
  23. }
  24. int main(){
  25. vector<unsigned short> line, line_cur;
  26. vector<vector<uint8_t > >par;
  27. string x,y;
  28.  
  29. getline(cin, x);
  30. getline(cin, y);
  31.  
  32. uint8_t siz;
  33. if((y.size())%4==0)
  34. siz=(y.size())/4;
  35. else
  36. siz=(y.size())/4+1;
  37. vector<uint8_t> temp2(siz,0);
  38. vector<char> ans;
  39.  
  40. for(unsigned short i=0;i<=x.size();++i)
  41.         par.push_back(temp2);
  42.        
  43. unsigned short m=x.size();
  44. unsigned short n=y.size();
  45. unsigned short cur;
  46.  
  47. for(unsigned short i=0;i<n+1;++i)
  48.         line.push_back(0);
  49.         unsigned short prev=0;
  50.    for(unsigned short i=1;i<m+1;++i){
  51.         line_cur.push_back(0);
  52.      for(unsigned short j=1;j<n+1;++j){
  53.        if(x[i-1]==y[j-1]){
  54.          cur=line[j-1]+1;
  55.          BIT_SET_VALUE(par[i][j],2*j%4,1);
  56.          }
  57.        else{
  58.          if(line[j]>=prev){
  59.            cur=line[j];
  60.            par[i][j]=2;
  61.            BIT_SET_VALUE(par[i][j],2*j%4+1,1);
  62.            }
  63.          else{
  64.            cur=prev;
  65.            BIT_SET_VALUE(par[i][j],2*j%4,1);
  66.            BIT_SET_VALUE(par[i][j],2*j%4+1,1);
  67.            }
  68.            }
  69.     prev=cur;
  70.     line_cur.push_back(cur);
  71.     }
  72.     line=line_cur;
  73.     prev=0;
  74.     line_cur.clear();
  75.     }
  76. while(true){
  77.         if(m==0||n==0)
  78.         break;
  79.         if(bit_check(par[m][n],2*n%4)&&!bit_check(par[m][n],2*n%4+1)){
  80.                 --m;
  81.                 --n;
  82.                 ans.push_back(x[m]);
  83.         }
  84.         else{
  85.                 if(!bit_check(par[m][n],2*n%4)&&bit_check(par[m][n],2*n%4+1))
  86.                         --m;
  87.                 else
  88.                         --n;
  89.         }
  90. }
  91. for(int i=ans.size()-1;i>=0;i--){
  92. cout<<ans[i];
  93. }
  94. cout<<endl;
  95. }