Advertisement
skimono

Untitled

Dec 21st, 2021
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <stdio.h>
  9. #include <stack>
  10. #include <deque>
  11. #include <queue>
  12. #include <set>
  13. #include <iterator>
  14. #include <map>
  15. #include <iomanip>
  16. #include <unordered_set>
  17. #include <array>
  18. #define int long long
  19. #define pb push_back
  20. #define fir first
  21. #define sec second
  22. #define double long double
  23. #define endl "\n"
  24. #define un unsigned
  25. #define INF 999999999999
  26. #define EPS 0.000000000001
  27. #define pii pair<int, int>
  28. #define all(v) v.begin(), v.end()
  29. using namespace std;
  30.  
  31. string mini(string a, string b)
  32. {
  33.     if ((a.size() <= b.size() && a != "$") || b == "$")
  34.     {
  35.         return a;
  36.     }
  37.  
  38.     return b;
  39. }
  40.  
  41. int check(char c)
  42. {
  43.     if (c == '*')
  44.     {
  45.         return 2;
  46.     }
  47.  
  48.     if (c == '?')
  49.     {
  50.         return 1;
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
  56. signed main()
  57. {
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(0);
  60.     cout.tie(0);
  61.  
  62.     string a, b;
  63.     cin >> a >> b;
  64.  
  65.     int n = a.size() + 1;
  66.     int m = b.size() + 1;
  67.  
  68.     a = "0" + a;
  69.     b = "0" + b;
  70.  
  71.     vector<vector<string>> dp(n, vector<string>(m));
  72.  
  73.     dp[0][0] = "0";
  74.  
  75.     // $ -- no solution
  76.  
  77.     for (int i = 1; i < n; i++)
  78.     {
  79.         if (a[i] == '*' && dp[i - 1][0] != "$")
  80.         {
  81.             dp[i][0] = dp[i - 1][0];
  82.         }
  83.         else
  84.         {
  85.             dp[i][0] = "$";
  86.         }
  87.     }
  88.  
  89.     for (int i = 1; i < m; i++)
  90.     {
  91.         if (b[i] == '*' && dp[0][i - 1] != "$")
  92.         {
  93.             dp[0][i] = dp[0][i - 1];
  94.         }
  95.         else
  96.         {
  97.             dp[0][i] = "$";
  98.         }
  99.     }
  100.  
  101.     for (int i = 1; i < n; i++)
  102.     {
  103.         for (int j = 1; j < m; j++)
  104.         {
  105.             if (a[i] == b[j] && a[i] != '*' && a[i] != '?')
  106.             {
  107.                 dp[i][j] = dp[i - 1][j - 1] + a[i];
  108.             }
  109.             else if (a[i] == b[j] && a[i] == '*')
  110.             {
  111.                 dp[i][j] = mini(dp[i][j - 1], dp[i - 1][j]);
  112.             }
  113.             else if (a[i] == b[j] && a[i] == '?')
  114.             {
  115.                 dp[i][j] = dp[i - 1][j - 1] + "a";
  116.             }
  117.            
  118.             if (dp[i][j] != "" && dp[i][j][0] == '$')
  119.             {
  120.                 dp[i][j] = "$";
  121.             }
  122.  
  123.             if (dp[i][j] != "")
  124.             {
  125.                 continue;
  126.             }
  127.  
  128.             if (check(a[i]) == 0)
  129.             {
  130.                 if (check(b[j]) == 1)
  131.                 {
  132.                     dp[i][j] = dp[i - 1][j - 1] + a[i];
  133.                 }
  134.                 else if (check(b[j]) == 2)
  135.                 {
  136.                     string lol = mini(dp[i - 1][j], dp[i][j - 1]);
  137.  
  138.                     if (lol == dp[i][j - 1])
  139.                     {
  140.                         dp[i][j] = lol;
  141.                     }
  142.                     else
  143.                     {
  144.                         dp[i][j] = lol + a[i];
  145.                     }
  146.                 }
  147.                 else
  148.                 {
  149.                     dp[i][j] = "$";
  150.                 }
  151.             }
  152.  
  153.             if (check(a[i]) == 1)
  154.             {
  155.                 if (check(b[j]) == 0)
  156.                 {
  157.                     dp[i][j] = dp[i - 1][j - 1] + b[j];
  158.                 }
  159.                 else
  160.                 {
  161.                     string lol = mini(dp[i - 1][j], dp[i][j - 1]);
  162.  
  163.                     if (lol == dp[i][j - 1])
  164.                     {
  165.                         dp[i][j] = lol;
  166.                     }
  167.                     else
  168.                     {
  169.                         dp[i][j] = lol + "a";
  170.                     }
  171.                 }
  172.             }
  173.  
  174.             if (check(a[i]) == 2)
  175.             {
  176.                 if (check(b[j]) == 0)
  177.                 {
  178.                     string lol = mini(dp[i - 1][j], dp[i][j - 1]);
  179.  
  180.                     if (lol == dp[i - 1][j])
  181.                     {
  182.                         dp[i][j] = lol;
  183.                     }
  184.                     else
  185.                     {
  186.                         dp[i][j] = lol + b[j];
  187.                     }
  188.                 }
  189.                 else
  190.                 {
  191.                     string lol = mini(dp[i - 1][j], dp[i][j - 1]);
  192.  
  193.                     if (lol == dp[i - 1][j])
  194.                     {
  195.                         dp[i][j] = lol;
  196.                     }
  197.                     else
  198.                     {
  199.                         dp[i][j] = lol + "a";
  200.                     }
  201.                 }
  202.             }
  203.  
  204.             if (dp[i][j][0] == '$')
  205.             {
  206.                 dp[i][j] = "$";
  207.             }
  208.  
  209.             dp[i][j];
  210.         }
  211.     }
  212.  
  213.  
  214.     if (dp[n - 1][m - 1] == "$")
  215.     {
  216.         cout << "No solution!";
  217.     }
  218.     else
  219.     {
  220.         for (int i = 1; i < dp[n - 1][m - 1].size(); i++)
  221.         {
  222.             cout << dp[n - 1][m - 1][i];
  223.         }
  224.     }
  225.  
  226.     return 0;
  227. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement