#include #include using namespace std; #define chmin(x, y) (x) = min((x), (y)) bool isMark(char c) { return c == '?' || c == '*'; } void pre(string &s) { int N = s.size(); for(int i = 0; i + 1 < N; i++) { if (!isMark(s[i]) && isMark(s[i + 1])) { swap(s[i], s[i + 1]); } } s += "$"; // 番兵. } bool validate(string s) { if (s.size() < 1 || s.size() > 2000) return false; if (isMark(s[0])) return false; for (int i = 0; i + 1 < s.size(); i++) { if (isMark(s[i]) && isMark(s[i + 1])) return false; } return true; } int main() { string A, B; cin >> A >> B; assert(validate(A) && validate(B)); int N = A.size(), M = B.size(); pre(A); pre(B); vector> dp(N + 1, vector(M + 1, 1 << 29)); dp[0][0] = 0; for(int i = 0; i <= N; i++) { for(int j = 0; j <= M; j++) { if (!isMark(A[i]) && !isMark(B[j])) { if (i + 1 <= N) chmin(dp[i + 1][j], dp[i][j] + 1); if (j + 1 <= M) chmin(dp[i][j + 1], dp[i][j] + 1); if (i + 1 <= N && j + 1 <= M) chmin(dp[i + 1][j + 1], dp[i][j] + (A[i] != B[j])); } else if (A[i] == '?' && !isMark(B[j])) { chmin(dp[i + 2][j], dp[i][j]); // ? でのマッチをやめる. if (j + 1 <= M) chmin(dp[i][j + 1], dp[i][j] + 1); // ?を温存して次の文字とマッチさせる if (j + 1 <= M) chmin(dp[i + 2][j + 1], dp[i][j] + (A[i + 1] != B[j])); // ?でのマッチを行う.*と違い,?のマッチを行うとiが進む(2回同じ?は使えない) } else if (!isMark(A[i]) && B[j] == '?') { chmin(dp[i][j + 2], dp[i][j]); if (i + 1 <= N) chmin(dp[i + 1][j], dp[i][j] + 1); if (i + 1 <= N) chmin(dp[i + 1][j + 2], dp[i][j] + (A[i] != B[j + 1])); } else if (A[i] == '*' && !isMark(B[j])) { chmin(dp[i + 2][j], dp[i][j]); // * でのマッチをやめる if (j + 1 <= M) chmin(dp[i][j + 1], dp[i][j] + 1); // * を温存して次の文字とマッチさせる if (j + 1 <= M) chmin(dp[i][j + 1], dp[i][j] + (A[i + 1] != B[j])); // *でのマッチを行う.この時,iが進まないので,再度この*でのマッチが行われる } else if (!isMark(A[i]) && B[j] == '*') { chmin(dp[i][j + 2], dp[i][j]); if (i + 1 <= N) chmin(dp[i + 1][j], dp[i][j] + 1); if (i + 1 <= N) chmin(dp[i + 1][j], dp[i][j] + (A[i] != B[j + 1])); } else { chmin(dp[i + 2][j], dp[i][j]); // B側のマークを残す //chmin(dp[i][j + 2], dp[i][j]); // A側のマークを残す } } } cout << dp[N][M] << endl; return 0; }