Advertisement
georgiy110802

Untitled

Feb 4th, 2022
835
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1000;
  6.  
  7. struct A
  8. {
  9.     int i, j;
  10.     char c;
  11. };
  12.  
  13. vector<vector<A>> pred;
  14. string s1, s2;
  15. char cc;
  16.  
  17. string to_s(char c)
  18. {
  19.     string s = "";
  20.     s.push_back(c);
  21.     return s;
  22. }
  23.  
  24. string get(int i, int j)
  25. {
  26.     if(i == 1 && j == 1)
  27.         return to_s(cc);
  28.     else
  29.         return get(pred[i][j].i, pred[i][j].j) + to_s(pred[i][j].c);
  30. }
  31.  
  32. int main()
  33. {
  34. //  ios::sync_with_stdio(0);
  35. //  cin.tie(0);
  36.     cin >> s1 >> s2;
  37.     int n = s1.size();
  38.     int m = s2.size();
  39.     s1.insert(s1.begin(), '#');
  40.     s2.insert(s2.begin(), '#');
  41.     vector<vector<int>> dp(n + 2, vector<int> (m + 2, INF));
  42.     pred.resize(n + 2, vector<A> (m + 2, {-1, -1, '-'}));
  43.     if(s1[1] == s2[1] || s1[1] == '?' || s1[1] == '*' || s2[1] == '?' || s2[1] == '*')
  44.     {
  45.         dp[1][1] = 1;
  46.         if(s1[1] == s2[1])
  47.         {
  48.             if(s1[1] == '?')
  49.                 cc = 'A';
  50.             else
  51.                 cc = s1[1];
  52.         }
  53.         else
  54.         {
  55.             if(s1[1] != '?' && s1[1] != '*')
  56.                 cc = s1[1];
  57.             else if(s2[1] != '?' && s2[1] != '*')
  58.                 cc = s2[1];
  59.             else
  60.                 cc = 'A';
  61.         }
  62.     }
  63. //  cout << "fff";
  64.     if(s1[1] == '*' && s2[1] == '*')
  65.         dp[1][1] = 0, cc = '-';
  66.     for(int i = 2; i <= n; i++)
  67.     {
  68.         if(s2[1] == '*' || s1[i] == '*')
  69.         {
  70.             if(s1[i] == '*' || s2[1] == s1[i])
  71.             {
  72.                 dp[i][1] = dp[i - 1][1];
  73.                 pred[i][1] = {i - 1, 1, '-'};
  74.             }
  75.             else
  76.             {
  77.                 dp[i][1] = dp[i - 1][1] + 1;
  78.                 pred[i][1] = {i - 1, 1, s1[i]};
  79.             }
  80.                
  81.         }
  82.         else
  83.             dp[i][1] = INF;
  84.     }
  85.     for(int i = 2; i <= m; i++)
  86.     {
  87.         if(s1[1] == '*' || s2[i] == '*')
  88.         {
  89.             if(s2[i] == '*' || s1[1] == s2[i])
  90.             {
  91.                 dp[1][i] = dp[1][i - 1];
  92.                 pred[1][i] = {1, i - 1, '-'};
  93.             }
  94.                
  95.             else
  96.             {
  97.                 dp[1][i] = dp[1][i - 1] + 1;
  98.                 pred[1][i] = {1, i - 1, s2[i]};
  99.             }
  100.                
  101.         }
  102.         else
  103.             dp[1][i] = INF;
  104.     }
  105. //  cout << "yyy";
  106.     for(int i = 2; i <= n; i++)
  107.     {
  108.         for(int j = 2; j <= m; j++)
  109.         {
  110.             if(s1[i] == '*' && s2[j] == '*')
  111.             {
  112.                 if(dp[i - 1][j] == INF && dp[i][j - 1] == INF)
  113.                 {
  114.                     dp[i][j] = INF;
  115.                     continue;
  116.                 }
  117.                 if(dp[i - 1][j] < dp[i][j - 1])
  118.                 {
  119.                     dp[i][j] = dp[i - 1][j];
  120.                     pred[i][j] = {i - 1, j, '-'};
  121.                 }
  122.                 else
  123.                 {
  124.                     dp[i][j] = dp[i][j - 1];
  125.                     pred[i][j] = {i, j - 1, '-'};
  126.                 }
  127. //              dp[i][j] = dp[i - 1][j - 1];
  128. //              pred[i][j] = {i - 1, j - 1, '-'};
  129.             }  
  130.             else if(s1[i] == s2[j] && s1[i] != '?' && s1[i] != '*')
  131.             {
  132.                 if(dp[i - 1][j - 1] == INF)
  133.                     dp[i][j] = INF;
  134.                 else
  135.                 {
  136.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  137.                     pred[i][j] = {i - 1, j - 1, s1[i]};
  138.                 }      
  139.             }
  140.             else if(s1[i] == '?' && s2[j] == '?')
  141.             {
  142.                 if(dp[i - 1][j - 1] == INF)
  143.                     dp[i][j] = INF;
  144.                 else
  145.                 {
  146.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  147.                     pred[i][j] = {i - 1, j - 1, 'A'};
  148.                 }
  149.                                
  150.             }
  151.             else if(s1[i] == '*')
  152.             {
  153.                 if(dp[i - 1][j] == INF && dp[i][j - 1] == INF)
  154.                 {
  155.                     dp[i][j] = INF;
  156.                     continue;
  157.                 }
  158.                 if(dp[i - 1][j] > dp[i][j - 1])
  159.                 {
  160.                     dp[i][j] = dp[i][j - 1] + 1;
  161.                     pred[i][j] = {i, j - 1, s2[j]};
  162.                 }  
  163.                 else
  164.                 {
  165.                     dp[i][j] = dp[i - 1][j];
  166.                     pred[i][j] = {i - 1, j, '-'};
  167.                 }  
  168. //              dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
  169. //              if(dp[i][j] != INF)
  170. //                  dp[i][j].push_back(f(s2[j - 1]));
  171.             }
  172.             else if(s2[j] == '*')
  173.             {
  174.                 if(dp[i - 1][j] == INF && dp[i][j - 1] == INF)
  175.                 {
  176.                     dp[i][j] = INF;
  177.                     continue;
  178.                 }
  179.                    
  180.                 if(dp[i - 1][j] < dp[i][j - 1])
  181.                 {
  182.                     dp[i][j] = dp[i - 1][j] + 1;
  183.                     pred[i][j] = {i - 1, j, s1[i]};
  184.                 }
  185.                 else
  186.                 {
  187.                     dp[i][j] = dp[i][j - 1];
  188.                     pred[i][j] = {i, j - 1, '-'};
  189.                 }
  190.                    
  191. //              dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
  192. //              if(dp[i][j] != INF)
  193. //                  dp[i][j].push_back(f(s1[i - 1]));
  194.             }
  195.             else if(s1[i] == '?')
  196.             {
  197.                 if(dp[i - 1][j - 1] == INF)
  198.                     dp[i][j] = INF;
  199.                 else
  200.                 {
  201.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  202.                     pred[i][j] = {i - 1, j - 1, s2[j]};
  203.                 }
  204.             }
  205.             else if(s2[j] == '?')
  206.             {
  207.                 if(dp[i - 1][j - 1] == INF)
  208.                     dp[i][j] = INF;
  209.                 else
  210.                 {
  211.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  212.                     pred[i][j] = {i - 1, j - 1, s1[i]};
  213.                 }
  214.             }
  215.             else
  216.                 dp[i][j] = INF;
  217.         }
  218.     }
  219. //  for(int i = 1; i <= n; i++)
  220. //  {
  221. //      for(int j = 1; j <= m; j++)
  222. //          cout << dp[i][j] << " ";
  223. //      cout << "\n";
  224. //  }
  225. //  cout << dp[n][m] << "\n";
  226.     if(dp[n][m] >= INF)
  227.     {
  228.         cout << "No solution!";
  229.         exit(0);//вероятно решение есть, но программа говорит, что его нет.
  230.     }
  231.        
  232.     if(dp[n][m] == 0)
  233.         cout << "A", exit(0);
  234.     string ans = get(n, m);
  235.     for(auto i : ans)
  236.     {
  237.         if(i == '?')
  238.             cout << "A";
  239.         else if(i != '-')
  240.             cout << i;
  241.     }
  242. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement