Raslboyy

217

Sep 12th, 2019
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     ifstream fin("input.txt");
  10.     ofstream fout("output.txt");
  11.  
  12.     string strA, strB;
  13.     fin >> strA >> strB;
  14.     int nA = strA.size();
  15.     int nB = strB.size();
  16.     strA = " " + strA; strB = " " + strB;
  17.     vector<vector<int>> dp(nA + 1, vector<int>(nB + 1));
  18.     for(int curA = 1; curA <= nA; curA++)
  19.         for (int curB = 1; curB <= nB; curB++) {
  20.             if (strA[curA] == '*') {
  21.                 for (int k = 0; k <= nB - curB; k++) {
  22.                     dp[curA][curB + k] = max(dp[curA][curB + k], dp[curA - 1][curB - 1] + k);
  23.                 }
  24.             }
  25.             else if (strB[curB] == '*') {
  26.                 for (int k = 0; k <= nA - curA; k++) {
  27.                     dp[curA + k][curB] = max(dp[curA + k][curB], dp[curA - 1][curB - 1] + k);
  28.                 }
  29.             }
  30.             else if (strA[curA] == strB[curB] || strA[curA] == '?' || strB[curB] == '?') {
  31.                 dp[curA][curB] = max(dp[curA][curB], dp[curA-1][curB-1] + 1);
  32.             }
  33.             else{
  34.                 dp[curA][curB] = max(dp[curA][curB - 1], dp[curA - 1][curB]);
  35.             }
  36.         }
  37.     fout << dp[nA][nB] << endl;
  38.  
  39.     fin.close();
  40.     fout.close();
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment