Raslboyy

217F

Sep 16th, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6. #include <functional>
  7.  
  8. #define mp make_pair
  9. #define x first
  10. #define y second
  11.  
  12. using namespace std;
  13.  
  14. typedef pair<int, int> pr;
  15.  
  16.  
  17. int main() {
  18.     ifstream fin("input.txt");
  19.     ofstream fout("output.txt");
  20.  
  21.     const int INF = 1e9;
  22.     string strA, strB;
  23.     fin >> strA >> strB;
  24.     int n = strA.size();
  25.     int m = strB.size();
  26.     strA += 'a';
  27.     strB += 'b';
  28.     vector<vector<int>> dp(n + 2, vector<int>(m + 2, INF));
  29.     vector<vector<pr>> prev(n + 2, vector<pr>(m + 2));
  30.     dp[0][0] = 0;
  31.     for (int i = 0; i <= n; i++)
  32.         for (int j = 0; j <= m; j++) {
  33.             if (dp[i][j] == INF) continue;
  34.             if (strA[i] == strB[j] || strA[i] == '?' || strB[j] == '?')
  35.                 if (dp[i][j] + 1 < dp[i + 1][j + 1]) {
  36.                     dp[i + 1][j + 1] = dp[i][j] + 1;
  37.                     prev[i + 1][j + 1] = mp(i, j);
  38.                 }
  39.             int tmp = 0;
  40.             if (strA[i] == '*' )
  41.                 for (int k = j; k <= m; k++) {
  42.                     if (dp[i][j] + k - j - tmp < dp[i + 1][k]) {
  43.                         dp[i + 1][k] = dp[i][j] + k - j - tmp;
  44.                         prev[i + 1][k] = mp(i, j);
  45.                     }
  46.                     tmp += (strB[k] == '*');
  47.                 }
  48.             tmp = 0;
  49.             if (strB[j] == '*')
  50.                 for (int k = i; k <= n; k++) {
  51.                     if (dp[i][j] + k - i - tmp < dp[k][j + 1]) {
  52.                         dp[k][j + 1] = dp[i][j] + k - i - tmp;
  53.                         prev[k][j + 1] = mp(i, j);
  54.                     }
  55.                     tmp += (strA[k] == '*');
  56.                 }
  57.         }
  58.     if (dp[n][m] == INF)
  59.         return fout << "No solution!" << endl, 0;
  60.    
  61.     function<void(int, int)> print = [&](int a, int b) {
  62.         if (!a && !b) return;
  63.         pr p = prev[a][b];
  64.         print(p.x, p.y);
  65.  
  66.         if (strA[p.x] == '*') {
  67.             for (int i = p.y; i < b; i++)
  68.                 if (strB[i] != '*')
  69.                     fout << (strB[i] == '?' ? 'A' : strB[i]);
  70.  
  71.             return;
  72.         }
  73.         if (strB[p.y] == '*') {
  74.             for (int i = p.x; i < a; i++)
  75.                 if (strA[i] != '*')
  76.                     fout << (strA[i] == '?' ? 'A' : strA[i]);
  77.            
  78.             return;
  79.         }
  80.         if (strA[p.x] == strB[p.y] || strA[p.x] == '?' || strB[p.y] == '?') {
  81.             if (strA[p.x] == '?' && strB[p.y] == '?')
  82.                 fout << 'A';
  83.             else
  84.                 fout << (strA[p.x] == '?' ? strB[p.y] : strA[p.x]);
  85.         }
  86.     };
  87.     print(n, m);
  88.  
  89.     fin.close();
  90.     fout.close();
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment