Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstring>
- #include<iostream>
- using namespace std;
- int main() {
- char *mas1=new char [1002];
- cin>>mas1;
- char *mas2=new char[1002];
- cin>>mas2;
- int n=strlen(mas1);
- int m=strlen(mas2);
- int **ans=new int *[n];
- for(int i=0; i<n; ++i)
- ans[i]=new int [m];
- if(mas1[0]==mas2[0])
- ans[0][0]=0;
- else
- ans[0][0]=1;
- for(int i=1; i<n; ++i){
- if(mas1[i]==mas2[0])
- ans[i][0]=max(ans[i-1][0],i);
- else
- ans[i][0]=ans[i-1][0]+1;
- }
- for(int j=1; j<m; ++j){
- if(mas1[0]==mas2[j])
- ans[0][j]=max(ans[0][j-1],j);
- else
- ans[0][j]=ans[0][j-1]+1;
- }
- for(int i=1; i<n; ++i){
- for(int j=1; j<m; ++j){
- if(mas1[i]!='?' && mas2[j]!='?' && mas1[i]!='*' && mas2[j]!='*'){
- if(mas1[i] == mas2[j]) {
- if (ans[i - 1][j - 1] != -1)
- ans[i][j] = ans[i - 1][j - 1] + 1;
- else
- ans[i][j] = -1;
- }
- else
- ans[i][j]=-1;
- }
- else if((mas1[i]=='?' && mas2[j]!='*') || (mas1[i]!='*' && mas2[j]=='?')){
- if(ans[i-1][j-1]!=-1)
- ans[i][j]=ans[i-1][j-1]+1;
- else
- ans[i][j]=-1;
- }
- else if((mas1[i]=='*' && mas2[j]!='*') || (mas1[i]!='*' && mas2[j]=='*'))
- ans[i][j]=min(ans[i-1][j],ans[i][j-1])+1;
- else if (mas1[i]== mas2[j] && mas1[i]=='*')
- ans[i][j]=min(ans[i-1][j], ans[i][j-1]);
- }
- }
- char *temp=new char [ans[n-1][m-1]];
- int flag=0;
- int i=n-1, j=m-1;
- while(i>=0 && j>=0){
- if(ans[i][j]==ans[i-1][j-1]+1 && mas1[i]==mas2[j] && mas1[i]!='?')
- temp[flag++]=mas1[i];
- else if (ans[i][j]==ans[i-1][j-1]+1 && (mas1[i]=='?' || mas2[j]=='?')){
- if(mas1[i]=='?')
- temp[flag++]=mas2[j];
- else
- temp[flag++]=mas1[i];
- }
- else if((ans[i][j]==ans[i-1][j]+1 || ans[i][j]==ans[i][j-1]+1) && (mas1[i]!='*' || mas2[j]!='*')){
- if(mas1[i]!='*')
- temp[flag++]=mas1[i];
- else
- temp[flag++]=mas2[j];
- }
- else if(ans[i][j]==-1){
- cout<<"Not Solurion!";
- return 0;
- }
- }
- for(int k=ans[n-1][m-1]-1; k>=0; --k)
- cout<<temp[k]<<" ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement