結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2019-08-30 23:09:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 2,446 bytes |
コンパイル時間 | 3,255 ms |
コンパイル使用メモリ | 174,588 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-11-22 02:45:55 |
合計ジャッジ時間 | 3,269 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; typedef pair<ll, P> P3; typedef pair<P, P> PP; constexpr ll MOD = ll(1e9 + 7); constexpr int IINF = INT_MAX; constexpr ll LLINF = LLONG_MAX; constexpr int MAX_N = int(1e5) + 5; constexpr double EPS = 1e-9; constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0}; #define REP(i, n) for (int i = 0; i < n; i++) #define REPR(i, n) for (int i = n; i >= 0; i--) #define SORT(v) sort((v).begin(), (v).end()) #define SORTR(v) sort((v).rbegin(), (v).rend()) #define ALL(v) (v).begin(), (v).end() int solve(vector<int> &a, vector<int> &b){ int n = a.size(), m = b.size(); vector<vector<int> > dp(n+1, vector<int>(m+1, IINF)); dp[0][0] = 0; for(int i=0;i<n;i++){ dp[i+1][0] = dp[i][0] + (a[i] < 26); } for(int j=0;j<m;j++){ dp[0][j+1] = dp[0][j] + (b[j] < 26); } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i]%26 == b[j]%26){ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]); } else{ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1); } dp[i+1][j+1] = min({dp[i+1][j+1], dp[i+1][j] + 1, dp[i][j+1] + 1}); if(a[i]>=26){ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1]); } if(b[j]>=26){ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j]); } if(a[i]>=52){ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + (a[i]%26!=b[j]%26)); } if(b[j]>=52){ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + (a[i]%26!=b[j]%26)); } } } return dp[n][m]; } int main() { int n, m; string A, B; cin >> A >> B; vector<int> a, b; n = A.size(); m = B.size(); A.push_back('#'); B.push_back('#'); for(int i=0;i<n;i++){ int c = A[i]-'a'; if(A[i+1] == '?'){ c += 26; i++; } else if(A[i+1] == '*'){ c += 52; i++; } a.push_back(c); } for(int i=0;i<m;i++){ int c = B[i]-'a'; if(B[i+1] == '?'){ c += 26; i++; } else if(B[i+1] == '*'){ c += 52; i++; } b.push_back(c); } cout << solve(a, b) << endl; return 0; }