結果
問題 | No.874 正規表現間距離 |
ユーザー |
|
提出日時 | 2019-08-30 23:37:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,081 bytes |
コンパイル時間 | 2,432 ms |
コンパイル使用メモリ | 198,916 KB |
最終ジャッジ日時 | 2025-01-07 16:06:05 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))using namespace std;template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); returnvector<decltype(cont)>(x, cont); }int solve(const string & a, const string & b) {auto dp = make_table(a.length() + 1, b.length() + 1, INT_MAX);dp[0][0] = 0;REP (i, a.size()) if (isalpha(a[i])) {REP (j, b.size()) if (isalpha(b[j])) {if (dp[i][j] == INT_MAX) continue;char a_op = (i + 1 < a.size() and not isalpha(a[i + 1]) ? a[i + 1] : '\0');char b_op = (j + 1 < b.size() and not isalpha(b[j + 1]) ? b[j + 1] : '\0');int ni = i + 1 + not not a_op;int nj = j + 1 + not not b_op;if (a[i] == b[j]) {chmin(dp[ni][nj], dp[i][j]);if (a_op == '*') chmin(dp[i][nj], dp[i][j]);if (b_op == '*') chmin(dp[ni][j], dp[i][j]);}if (a_op) chmin(dp[ni][j], dp[i][j]);if (b_op) chmin(dp[i][nj], dp[i][j]);chmin(dp[ni][j], dp[i][j] + 1);chmin(dp[i][nj], dp[i][j] + 1);chmin(dp[ni][nj], dp[i][j] + 1);}}REP (j, b.size()) if (isalpha(b[j])) {int i = a.size();char b_op = (j + 1 < b.size() and not isalpha(b[j + 1]) ? b[j + 1] : '\0');int nj = j + 1 + not not b_op;chmin(dp[i][nj], dp[i][j] + not b_op);}REP (i, a.size()) if (isalpha(a[i])) {int j = b.size();char a_op = (i + 1 < a.size() and not isalpha(a[i + 1]) ? a[i + 1] : '\0');int ni = i + 1 + not not a_op;chmin(dp[ni][j], dp[i][j] + not a_op);}return dp[a.size()][b.size()];}int main() {string a, b; cin >> a >> b;cout << solve(a, b) << endl;return 0;}