Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <functional>
- #define mp make_pair
- #define x first
- #define y second
- using namespace std;
- typedef pair<int, int> pr;
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- const int INF = 1e9;
- string strA, strB;
- fin >> strA >> strB;
- int n = strA.size();
- int m = strB.size();
- strA += 'a';
- strB += 'b';
- vector<vector<int>> dp(n + 2, vector<int>(m + 2, INF));
- vector<vector<pr>> prev(n + 2, vector<pr>(m + 2));
- dp[0][0] = 0;
- for (int i = 0; i <= n; i++)
- for (int j = 0; j <= m; j++) {
- if (dp[i][j] == INF) continue;
- if (strA[i] == strB[j] || strA[i] == '?' || strB[j] == '?')
- if (dp[i][j] + 1 < dp[i + 1][j + 1]) {
- dp[i + 1][j + 1] = dp[i][j] + 1;
- prev[i + 1][j + 1] = mp(i, j);
- }
- int tmp = 0;
- if (strA[i] == '*' )
- for (int k = j; k <= m; k++) {
- if (dp[i][j] + k - j - tmp < dp[i + 1][k]) {
- dp[i + 1][k] = dp[i][j] + k - j - tmp;
- prev[i + 1][k] = mp(i, j);
- }
- tmp += (strB[k] == '*');
- }
- tmp = 0;
- if (strB[j] == '*')
- for (int k = i; k <= n; k++) {
- if (dp[i][j] + k - i - tmp < dp[k][j + 1]) {
- dp[k][j + 1] = dp[i][j] + k - i - tmp;
- prev[k][j + 1] = mp(i, j);
- }
- tmp += (strA[k] == '*');
- }
- }
- if (dp[n][m] == INF)
- return fout << "No solution!" << endl, 0;
- function<void(int, int)> print = [&](int a, int b) {
- if (!a && !b) return;
- pr p = prev[a][b];
- print(p.x, p.y);
- if (strA[p.x] == '*') {
- for (int i = p.y; i < b; i++)
- if (strB[i] != '*')
- fout << (strB[i] == '?' ? 'A' : strB[i]);
- return;
- }
- if (strB[p.y] == '*') {
- for (int i = p.x; i < a; i++)
- if (strA[i] != '*')
- fout << (strA[i] == '?' ? 'A' : strA[i]);
- return;
- }
- if (strA[p.x] == strB[p.y] || strA[p.x] == '?' || strB[p.y] == '?') {
- if (strA[p.x] == '?' && strB[p.y] == '?')
- fout << 'A';
- else
- fout << (strA[p.x] == '?' ? strB[p.y] : strA[p.x]);
- }
- };
- print(n, m);
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment