Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.91 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. #include<bitset>
  4. #include<cstdio>
  5. #include<cmath>
  6. #include<map>
  7. #include<algorithm>
  8. #include<set>
  9. #include<stack>
  10. #include<queue>
  11. #include<fstream>
  12. #include<vector>
  13.  
  14. int aa[300][300];
  15. int spec[300];
  16. long dp[100][100];
  17. bool was[15][15];
  18. int inf = 100000000;
  19. using namespace std;
  20.  
  21. void multiply(int* a, int m)
  22. {
  23.     int del = 0;
  24.     for(int j = 1; j <= a[0]; j++)
  25.         {
  26.             a[j] = a[j] * m + del;
  27.             del = a[j] / 10;
  28.             a[j] -= del * 10;
  29.         }  
  30.     while(del > 0)
  31.         {
  32.             a[0]++;
  33.             a[a[0]] = del % 10;
  34.             del /= 10;
  35.         }
  36.     return;
  37. }
  38.  
  39. void summarise(int* a, int* b, int* c)
  40.     {
  41.     int del = 0;
  42.     a[0] = max(a[0],b[0]);
  43.     c[0] = a[0];
  44.     for(int i = 1; i <= a[0]; i++)
  45.     {  
  46.     c[i] = a[i] + b[i] + del;
  47.     if(c[i] >= 10)
  48.         {
  49.         del = 1;
  50.         c[i] -= 10;
  51.         }
  52.     else
  53.         del = 0;       
  54.     }
  55.     if(del > 0)
  56.     {
  57.         c[0]++;
  58.         c[c[0]] = del;
  59.     }
  60.     return;
  61. }
  62.  
  63.  
  64. int main()
  65. {
  66. string s1,s2;
  67. cin >> s1 >> s2;
  68. int n = s1.size(), m = s2.size();
  69. dp[0][0] = 0;
  70. for(int j = 1; j <=m; j++)
  71.     {
  72.         if(dp[0][j-1] == inf or s2[j-1] != '*')
  73.             dp[0][j] = inf;
  74.     }
  75. for(int i = 1; i <=n; i++)
  76.     {
  77.         if(dp[i-1][0] == inf or s1[i-1] != '*')
  78.             dp[i][0] = inf;
  79.     }
  80.  
  81. for(int i = 1; i <= n; i++)
  82.     {
  83.         for(int j = 1; j <= m; j++)
  84.             {
  85.                 if( s1[i-1] <= 'z' and s1[i-1] >= 'A' and s2[j-1] <= 'z' and s2[j-1] >= 'A')
  86.                 {
  87.                     if(s1[i-1] == s2[j-1] and dp[i-1][j-1] != inf)
  88.                             dp[i][j] = dp[i-1][j-1] + 1;
  89.                     else
  90.                         dp[i][j] = inf;
  91.                 }
  92.                 else if( ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?'))
  93.                     {
  94.                         if(dp[i-1][j-1] != inf)
  95.                             dp[i][j] = dp[i-1][j-1] + 1;
  96.                         else
  97.                             dp[i][j] = inf;
  98.                     }
  99.                 else if(s1[i-1] == '*' and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?') )
  100.                     {
  101.                         if(dp[i][j - 1] < dp[i-1][j] /*and dp[i][j-1] != -1 */)
  102.                                 dp[i][j] = dp[i][j-1] + 1;
  103.                         else /*if(dp[i-1][j] != -1)*/  
  104.                                 dp[i][j] = dp[i-1][j];
  105.                     }
  106.                 else if(s2[j-1] == '*' and ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') )
  107.                     {
  108.                         if(dp[i][j - 1] <= dp[i-1][j] /*and dp[i][j-1] != -1 */)
  109.                             dp[i][j] = dp[i][j-1];
  110.                         else /*if(dp[i-1][j] != -1)*/  
  111.                                 dp[i][j] = dp[i-1][j] + 1;
  112.                     }
  113.                 else if(s1[i-1] == '*' and s2[j-1] == '*')
  114.                     {
  115.                         if(dp[i][j - 1] <= dp[i-1][j])
  116.                             dp[i][j] = dp[i][j-1];
  117.                         else   
  118.                             dp[i][j] = dp[i-1][j];
  119.                     }
  120.             }
  121.     }
  122.  
  123. if(dp[n][m] >= inf)
  124.     {
  125.         cout << "No solution!";
  126.         return 0;
  127.     }
  128.  
  129. stack <char> st;
  130. for(int i = n, j = m; i >= 1 and j >= 1;)
  131.     {
  132.         if( s1[i-1] <= 'z' and s1[i-1] >= 'A' and s2[j-1] <= 'z' and s2[j-1] >= 'A')
  133.                 {
  134.                     st.push(s1[i-1]);
  135.                     i--;
  136.                     j--;
  137.                 }
  138.                 else if( ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?'))
  139.                     {
  140.                         if(s1[i-1] == '?' and s2[j-1] == '?')
  141.                             st.push('A');
  142.                         else if(s1[i-1] == '?')
  143.                             st.push(s2[j-1]);
  144.                         else
  145.                             st.push(s1[i-1]);
  146.                         i--;
  147.                         j--;
  148.                     }
  149.                 else if(s1[i-1] == '*' and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?') )
  150.                     {
  151.                         if(dp[i][j - 1] < dp[i-1][j])
  152.                                 {
  153.                                     //dp[i][j] = dp[i][j-1] + 1;
  154.                                     if(s2[j-1] == '?')
  155.                                         st.push('A');
  156.                                     else
  157.                                         st.push(s2[j-1]);
  158.                                     j--;
  159.                                 }
  160.                         else    
  161.                             //dp[i][j] = dp[i-1][j];
  162.                             i--;
  163.                     }
  164.                 else if(s2[j-1] == '*' and ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') )
  165.                     {
  166.                         if(dp[i][j - 1] <= dp[i-1][j])
  167.                             j--;
  168.                         else   
  169.                             {
  170.                                 if(s1[i-1] == '?')
  171.                                     st.push('A');
  172.                                 else
  173.                                     st.push(s1[i-1]);
  174.                                 i--;
  175.                             }
  176.                                
  177.                     }
  178.                 else if(s1[i-1] == '*' and s2[j-1] == '*')
  179.                     {
  180.                         if(dp[i][j - 1] <= dp[i-1][j])
  181.                             j--;
  182.                         else   
  183.                             i--;
  184.                     }
  185.             }
  186. while(!st.empty())
  187.     {
  188.         cout << st.top();
  189.         st.pop();
  190.     }
  191. return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement