Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- string strA, strB;
- fin >> strA >> strB;
- int nA = strA.size();
- int nB = strB.size();
- strA = " " + strA; strB = " " + strB;
- vector<vector<int>> dp(nA + 1, vector<int>(nB + 1));
- for(int curA = 1; curA <= nA; curA++)
- for (int curB = 1; curB <= nB; curB++) {
- if (strA[curA] == '*') {
- for (int k = 0; k <= nB - curB; k++) {
- dp[curA][curB + k] = max(dp[curA][curB + k], dp[curA - 1][curB - 1] + k);
- }
- }
- else if (strB[curB] == '*') {
- for (int k = 0; k <= nA - curA; k++) {
- dp[curA + k][curB] = max(dp[curA + k][curB], dp[curA - 1][curB - 1] + k);
- }
- }
- else if (strA[curA] == strB[curB] || strA[curA] == '?' || strB[curB] == '?') {
- dp[curA][curB] = max(dp[curA][curB], dp[curA-1][curB-1] + 1);
- }
- else{
- dp[curA][curB] = max(dp[curA][curB - 1], dp[curA - 1][curB]);
- }
- }
- fout << dp[nA][nB] << endl;
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment