結果
問題 | No.874 正規表現間距離 |
ユーザー |
|
提出日時 | 2019-08-30 23:00:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,983 bytes |
コンパイル時間 | 1,765 ms |
コンパイル使用メモリ | 174,936 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-11-22 02:14:26 |
合計ジャッジ時間 | 3,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<char, char>;vector<P> calc(string& s) {int n = s.size();vector<P> res;for (int i = 0; i < n; ) {if (i < n - 1) {if (s[i + 1] == '?' || s[i + 1] == '*') {res.emplace_back(s[i], s[i + 1]);i += 2;} else {res.emplace_back(s[i], s[i]);i++;}} else {res.emplace_back(s[i], s[i]);break;}}return res;}const int INF = 1e9;int main() {cin.tie(0);ios::sync_with_stdio(false);string a, b;cin >> a >> b;vector<P> va = calc(a);vector<P> vb = calc(b);int na = va.size();int nb = vb.size();vector< vector<int> > dp(na + 1, vector<int>(nb + 1, INF));dp[0][0] = 0;for (int i = 1; i <= na; i++) {dp[i][0] = dp[i - 1][0];if (va[i - 1].second == '?' || va[i - 1].second == '*') continue;dp[i][0]++;}for (int i = 1; i <= nb; i++) {dp[0][i] = dp[0][i - 1];if (vb[i - 1].second == '?' || vb[i - 1].second == '*') continue;dp[0][i]++;}for (int i = 0; i < na; i++) {for (int j = 0; j < nb; j++) {int cost = (va[i].first != vb[j].first);int hoge = dp[i][j];if (va[i].second == '*') hoge = min(hoge, dp[i + 1][j]);if (vb[j].second == '*') hoge = min(hoge, dp[i][j + 1]);dp[i + 1][j + 1] = min({dp[i + 1][j + 1],hoge + cost,dp[i][j + 1] + (va[i].first == va[i].second),dp[i + 1][j] + (vb[j].first == vb[j].second)});}}/*for (int i = 0; i <= na; i++) {for (int j = 0; j <= nb; j++) {cerr << i << " " << j << ": " << dp[i][j] << endl;}}//*/cout << dp[na][nb] << endl;return 0;}