daily pastebin goal
66%
SHARE
TWEET

Untitled

a guest Feb 13th, 2018 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<cstring>
  2. #include<iostream>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     char *mas1=new char [1002];
  8.     cin>>mas1;
  9.  
  10.     char *mas2=new char[1002];
  11.     cin>>mas2;
  12.  
  13.     int n=strlen(mas1);
  14.     int m=strlen(mas2);
  15.  
  16.     int **ans=new int *[n];
  17.     for(int i=0; i<n; ++i)
  18.         ans[i]=new int [m];
  19.  
  20.  
  21.     if(mas1[0]==mas2[0])
  22.         ans[0][0]=0;
  23.     else
  24.         ans[0][0]=1;
  25.  
  26.     for(int i=1; i<n; ++i){
  27.         if(mas1[i]==mas2[0])
  28.             ans[i][0]=max(ans[i-1][0],i);
  29.         else
  30.             ans[i][0]=ans[i-1][0]+1;
  31.     }
  32.  
  33.     for(int j=1; j<m; ++j){
  34.         if(mas1[0]==mas2[j])
  35.             ans[0][j]=max(ans[0][j-1],j);
  36.         else
  37.             ans[0][j]=ans[0][j-1]+1;
  38.     }
  39.  
  40.  
  41.     for(int i=1; i<n; ++i){
  42.         for(int j=1; j<m; ++j){
  43.  
  44.             if(mas1[i]!='?' && mas2[j]!='?' && mas1[i]!='*' && mas2[j]!='*'){
  45.                 if(mas1[i] == mas2[j]) {
  46.                     if (ans[i - 1][j - 1] != -1)
  47.                         ans[i][j] = ans[i - 1][j - 1] + 1;
  48.                     else
  49.                         ans[i][j] = -1;
  50.                 }
  51.                 else
  52.                     ans[i][j]=-1;
  53.             }
  54.  
  55.             else if((mas1[i]=='?' && mas2[j]!='*') || (mas1[i]!='*' && mas2[j]=='?')){
  56.                 if(ans[i-1][j-1]!=-1)
  57.                     ans[i][j]=ans[i-1][j-1]+1;
  58.                 else
  59.                     ans[i][j]=-1;
  60.             }
  61.  
  62.             else if((mas1[i]=='*' && mas2[j]!='*') || (mas1[i]!='*' && mas2[j]=='*'))
  63.                 ans[i][j]=min(ans[i-1][j],ans[i][j-1])+1;
  64.  
  65.             else if (mas1[i]== mas2[j] && mas1[i]=='*')
  66.                 ans[i][j]=min(ans[i-1][j], ans[i][j-1]);
  67.  
  68.         }
  69.     }
  70.  
  71.     char *temp=new char [ans[n-1][m-1]];
  72.     int flag=0;
  73.     int i=n-1, j=m-1;
  74.     while(i>=0 && j>=0){
  75.  
  76.             if(ans[i][j]==ans[i-1][j-1]+1 && mas1[i]==mas2[j] && mas1[i]!='?')
  77.                 temp[flag++]=mas1[i];
  78.  
  79.             else if (ans[i][j]==ans[i-1][j-1]+1 && (mas1[i]=='?' || mas2[j]=='?')){
  80.                 if(mas1[i]=='?')
  81.                     temp[flag++]=mas2[j];
  82.                 else
  83.                     temp[flag++]=mas1[i];
  84.             }
  85.  
  86.             else if((ans[i][j]==ans[i-1][j]+1 || ans[i][j]==ans[i][j-1]+1) && (mas1[i]!='*' || mas2[j]!='*')){
  87.                 if(mas1[i]!='*')
  88.                     temp[flag++]=mas1[i];
  89.                 else
  90.                     temp[flag++]=mas2[j];
  91.             }
  92.             else if(ans[i][j]==-1){
  93.                 cout<<"Not Solurion!";
  94.                 return 0;
  95.             }
  96.  
  97.     }
  98.  
  99.     for(int k=ans[n-1][m-1]-1; k>=0; --k)
  100.         cout<<temp[k]<<" ";
  101.     return 0;
  102. }
RAW Paste Data
Top