Advertisement
Guest User

Untitled

a guest
Feb 13th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement