Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- #include<bitset>
- #include<cstdio>
- #include<cmath>
- #include<map>
- #include<algorithm>
- #include<set>
- #include<stack>
- #include<queue>
- #include<fstream>
- #include<vector>
- int aa[300][300];
- int spec[300];
- long dp[100][100];
- bool was[15][15];
- int inf = 100000000;
- using namespace std;
- void multiply(int* a, int m)
- {
- int del = 0;
- for(int j = 1; j <= a[0]; j++)
- {
- a[j] = a[j] * m + del;
- del = a[j] / 10;
- a[j] -= del * 10;
- }
- while(del > 0)
- {
- a[0]++;
- a[a[0]] = del % 10;
- del /= 10;
- }
- return;
- }
- void summarise(int* a, int* b, int* c)
- {
- int del = 0;
- a[0] = max(a[0],b[0]);
- c[0] = a[0];
- for(int i = 1; i <= a[0]; i++)
- {
- c[i] = a[i] + b[i] + del;
- if(c[i] >= 10)
- {
- del = 1;
- c[i] -= 10;
- }
- else
- del = 0;
- }
- if(del > 0)
- {
- c[0]++;
- c[c[0]] = del;
- }
- return;
- }
- int main()
- {
- string s1,s2;
- cin >> s1 >> s2;
- int n = s1.size(), m = s2.size();
- dp[0][0] = 0;
- for(int j = 1; j <=m; j++)
- {
- if(dp[0][j-1] == inf or s2[j-1] != '*')
- dp[0][j] = inf;
- }
- for(int i = 1; i <=n; i++)
- {
- if(dp[i-1][0] == inf or s1[i-1] != '*')
- dp[i][0] = inf;
- }
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- if( s1[i-1] <= 'z' and s1[i-1] >= 'A' and s2[j-1] <= 'z' and s2[j-1] >= 'A')
- {
- if(s1[i-1] == s2[j-1] and dp[i-1][j-1] != inf)
- dp[i][j] = dp[i-1][j-1] + 1;
- else
- dp[i][j] = inf;
- }
- else if( ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?'))
- {
- if(dp[i-1][j-1] != inf)
- dp[i][j] = dp[i-1][j-1] + 1;
- else
- dp[i][j] = inf;
- }
- else if(s1[i-1] == '*' and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?') )
- {
- if(dp[i][j - 1] < dp[i-1][j] /*and dp[i][j-1] != -1 */)
- dp[i][j] = dp[i][j-1] + 1;
- else /*if(dp[i-1][j] != -1)*/
- dp[i][j] = dp[i-1][j];
- }
- else if(s2[j-1] == '*' and ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') )
- {
- if(dp[i][j - 1] <= dp[i-1][j] /*and dp[i][j-1] != -1 */)
- dp[i][j] = dp[i][j-1];
- else /*if(dp[i-1][j] != -1)*/
- dp[i][j] = dp[i-1][j] + 1;
- }
- else if(s1[i-1] == '*' and s2[j-1] == '*')
- {
- if(dp[i][j - 1] <= dp[i-1][j])
- dp[i][j] = dp[i][j-1];
- else
- dp[i][j] = dp[i-1][j];
- }
- }
- }
- if(dp[n][m] >= inf)
- {
- cout << "No solution!";
- return 0;
- }
- stack <char> st;
- for(int i = n, j = m; i >= 1 and j >= 1;)
- {
- if( s1[i-1] <= 'z' and s1[i-1] >= 'A' and s2[j-1] <= 'z' and s2[j-1] >= 'A')
- {
- st.push(s1[i-1]);
- i--;
- j--;
- }
- else if( ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?'))
- {
- if(s1[i-1] == '?' and s2[j-1] == '?')
- st.push('A');
- else if(s1[i-1] == '?')
- st.push(s2[j-1]);
- else
- st.push(s1[i-1]);
- i--;
- j--;
- }
- else if(s1[i-1] == '*' and ((s2[j-1] >= 'A' and s2[j-1] <= 'z') or s2[j-1] == '?') )
- {
- if(dp[i][j - 1] < dp[i-1][j])
- {
- //dp[i][j] = dp[i][j-1] + 1;
- if(s2[j-1] == '?')
- st.push('A');
- else
- st.push(s2[j-1]);
- j--;
- }
- else
- //dp[i][j] = dp[i-1][j];
- i--;
- }
- else if(s2[j-1] == '*' and ((s1[i-1] >= 'A' and s1[i-1] <= 'z') or s1[i-1] == '?') )
- {
- if(dp[i][j - 1] <= dp[i-1][j])
- j--;
- else
- {
- if(s1[i-1] == '?')
- st.push('A');
- else
- st.push(s1[i-1]);
- i--;
- }
- }
- else if(s1[i-1] == '*' and s2[j-1] == '*')
- {
- if(dp[i][j - 1] <= dp[i-1][j])
- j--;
- else
- i--;
- }
- }
- while(!st.empty())
- {
- cout << st.top();
- st.pop();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement