Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int INF = 1000;
- struct A
- {
- int i, j;
- char c;
- };
- vector<vector<A>> pred;
- string s1, s2;
- char cc;
- string to_s(char c)
- {
- string s = "";
- s.push_back(c);
- return s;
- }
- string get(int i, int j)
- {
- if(i == 1 && j == 1)
- return to_s(cc);
- else
- return get(pred[i][j].i, pred[i][j].j) + to_s(pred[i][j].c);
- }
- int main()
- {
- // ios::sync_with_stdio(0);
- // cin.tie(0);
- cin >> s1 >> s2;
- int n = s1.size();
- int m = s2.size();
- s1.insert(s1.begin(), '#');
- s2.insert(s2.begin(), '#');
- vector<vector<int>> dp(n + 2, vector<int> (m + 2, INF));
- pred.resize(n + 2, vector<A> (m + 2, {-1, -1, '-'}));
- if(s1[1] == s2[1] || s1[1] == '?' || s1[1] == '*' || s2[1] == '?' || s2[1] == '*')
- {
- dp[1][1] = 1;
- if(s1[1] == s2[1])
- {
- if(s1[1] == '?')
- cc = 'A';
- else
- cc = s1[1];
- }
- else
- {
- if(s1[1] != '?' && s1[1] != '*')
- cc = s1[1];
- else if(s2[1] != '?' && s2[1] != '*')
- cc = s2[1];
- else
- cc = 'A';
- }
- }
- // cout << "fff";
- if(s1[1] == '*' && s2[1] == '*')
- dp[1][1] = 0, cc = '-';
- for(int i = 2; i <= n; i++)
- {
- if(s2[1] == '*' || s1[i] == '*')
- {
- if(s1[i] == '*' || s2[1] == s1[i])
- {
- dp[i][1] = dp[i - 1][1];
- pred[i][1] = {i - 1, 1, '-'};
- }
- else
- {
- dp[i][1] = dp[i - 1][1] + 1;
- pred[i][1] = {i - 1, 1, s1[i]};
- }
- }
- else
- dp[i][1] = INF;
- }
- for(int i = 2; i <= m; i++)
- {
- if(s1[1] == '*' || s2[i] == '*')
- {
- if(s2[i] == '*' || s1[1] == s2[i])
- {
- dp[1][i] = dp[1][i - 1];
- pred[1][i] = {1, i - 1, '-'};
- }
- else
- {
- dp[1][i] = dp[1][i - 1] + 1;
- pred[1][i] = {1, i - 1, s2[i]};
- }
- }
- else
- dp[1][i] = INF;
- }
- // cout << "yyy";
- for(int i = 2; i <= n; i++)
- {
- for(int j = 2; j <= m; j++)
- {
- if(s1[i] == '*' && s2[j] == '*')
- {
- if(dp[i - 1][j] == INF && dp[i][j - 1] == INF)
- {
- dp[i][j] = INF;
- continue;
- }
- if(dp[i - 1][j] < dp[i][j - 1])
- {
- dp[i][j] = dp[i - 1][j];
- pred[i][j] = {i - 1, j, '-'};
- }
- else
- {
- dp[i][j] = dp[i][j - 1];
- pred[i][j] = {i, j - 1, '-'};
- }
- // dp[i][j] = dp[i - 1][j - 1];
- // pred[i][j] = {i - 1, j - 1, '-'};
- }
- else if(s1[i] == s2[j] && s1[i] != '?' && s1[i] != '*')
- {
- if(dp[i - 1][j - 1] == INF)
- dp[i][j] = INF;
- else
- {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- pred[i][j] = {i - 1, j - 1, s1[i]};
- }
- }
- else if(s1[i] == '?' && s2[j] == '?')
- {
- if(dp[i - 1][j - 1] == INF)
- dp[i][j] = INF;
- else
- {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- pred[i][j] = {i - 1, j - 1, 'A'};
- }
- }
- else if(s1[i] == '*')
- {
- if(dp[i - 1][j] == INF && dp[i][j - 1] == INF)
- {
- dp[i][j] = INF;
- continue;
- }
- if(dp[i - 1][j] > dp[i][j - 1])
- {
- dp[i][j] = dp[i][j - 1] + 1;
- pred[i][j] = {i, j - 1, s2[j]};
- }
- else
- {
- dp[i][j] = dp[i - 1][j];
- pred[i][j] = {i - 1, j, '-'};
- }
- // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
- // if(dp[i][j] != INF)
- // dp[i][j].push_back(f(s2[j - 1]));
- }
- else if(s2[j] == '*')
- {
- if(dp[i - 1][j] == INF && dp[i][j - 1] == INF)
- {
- dp[i][j] = INF;
- continue;
- }
- if(dp[i - 1][j] < dp[i][j - 1])
- {
- dp[i][j] = dp[i - 1][j] + 1;
- pred[i][j] = {i - 1, j, s1[i]};
- }
- else
- {
- dp[i][j] = dp[i][j - 1];
- pred[i][j] = {i, j - 1, '-'};
- }
- // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
- // if(dp[i][j] != INF)
- // dp[i][j].push_back(f(s1[i - 1]));
- }
- else if(s1[i] == '?')
- {
- if(dp[i - 1][j - 1] == INF)
- dp[i][j] = INF;
- else
- {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- pred[i][j] = {i - 1, j - 1, s2[j]};
- }
- }
- else if(s2[j] == '?')
- {
- if(dp[i - 1][j - 1] == INF)
- dp[i][j] = INF;
- else
- {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- pred[i][j] = {i - 1, j - 1, s1[i]};
- }
- }
- else
- dp[i][j] = INF;
- }
- }
- // for(int i = 1; i <= n; i++)
- // {
- // for(int j = 1; j <= m; j++)
- // cout << dp[i][j] << " ";
- // cout << "\n";
- // }
- // cout << dp[n][m] << "\n";
- if(dp[n][m] >= INF)
- {
- cout << "No solution!";
- exit(0);//вероятно решение есть, но программа говорит, что его нет.
- }
- if(dp[n][m] == 0)
- cout << "A", exit(0);
- string ans = get(n, m);
- for(auto i : ans)
- {
- if(i == '?')
- cout << "A";
- else if(i != '-')
- cout << i;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement