結果

問題 No.874 正規表現間距離
コンテスト
ユーザー WutongDeath
提出日時 2026-07-26 15:04:41
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 22 ms / 2,000 ms
+ 518µs
コード長 1,268 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,666 ms
コンパイル使用メモリ 169,812 KB
実行使用メモリ 19,840 KB
最終ジャッジ日時 2026-07-26 15:04:47
合計ジャッジ時間 4,202 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 2010;

struct Atom {
    char ch, mark;
};

string a, b;
Atom x[N], y[N];
int f[N][N], n, m;

void ChMin(int &x, int y) {
    x = min(x, y);
}

int Parse(const string &s, Atom atom[]) {
    int sz = 0, len = s.size();
    for (int i = 0; i < len; ++i) {
        ++sz;
        atom[sz] = { s[i], 0 };
        if (i + 1 < len && (s[i + 1] == '?' || s[i + 1] == '*')) {
            atom[sz].mark = s[++i];
        }
    }
    return sz;
}

int main() {
    cin >> a >> b;
    n = Parse(a, x), m = Parse(b, y);
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i < n) ChMin(f[i + 1][j], f[i][j] + (x[i + 1].mark == 0));
            if (j < m) ChMin(f[i][j + 1], f[i][j] + (y[j + 1].mark == 0));
            if (i < n && j < m) {
                int ni = i + (x[i + 1].mark != '*');
                int nj = j + (y[j + 1].mark != '*');
                if (ni != i || nj != j) {
                    ChMin(f[ni][nj], f[i][j] + (x[i + 1].ch != y[j + 1].ch));
                }
            }
        }
    }

    printf("%d\n", f[n][m]);

    return 0;
}
0