#1173762 (C++14) No.874 正規表現間距離

• 問題: No.874 正規表現間距離
• ユーザー: zelda_master
• 提出日時: 2026-07-26 16:09:21
• 言語: C++14 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 21 ms / 2,000 ms
• コード長: 4,407 bytes
• コンパイル時間: 2,068 ms
• コンパイル使用メモリ: 77,916 KB
• 実行使用メモリ: 19,840 KB
• 最終ジャッジ日時: 2026-07-26 16:12:48
• 合計ジャッジ時間: 2,686 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 4
other	AC * 38

ソースコード

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

using namespace std;

const int N = 2010;

struct Atom {
    char ch1, ch2;
};

int f[N][N];
string a, b;
Atom atoms[2][N];

int Parse(string s, int op) {
    int cnt = 0, n = s.size();
    for (int i = 0; i < n; ++i) {
        atoms[op][++cnt].ch1 = s[i];
        if (i + 1 < n && (s[i + 1] == '?' || s[i + 1] == '*')) atoms[op][cnt].ch2 = s[++i];
        else atoms[op][cnt].ch2 = ' ';
    }
    return cnt;
}

/**
 * 问题：从 $A,B$ 各自能生成的字符串中各选一个，求这两个字符串的最小编辑距离。
 *
 * 线索：
 *   - 长度不超过 $2000$，可以记录“$A$ 处理到哪里、$B$ 处理到哪里”这两个位置，
 *     使用 $\mathcal{O}(nm)$ 的二维动态规划。
 *   - `?` 和 `*` 都只影响紧挨在它们前面的一个字母，所以可以先把表达式分段。
 *
 * 思维链：
 *   1. 先把表达式按“一个字母以及它后面的 `?` 或 `*`”分段。
 *      例如 `ab?c*` 分成 `a`、`b?`、`c*`。代码把这样的一段命名为 Atom（原子）。
 *      `?`、`*` 叫量词，在本题中只表示这一段的字母可以出现多少次。
 *   2. 两个具体字符串的编辑过程可以从左到右排成三种动作：
 *      只取 $A$ 的一个字母就是删除，只取 $B$ 的一个字母就是插入，
 *      两边各取一个字母就是匹配或替换。
 *   3. 因此不必真的把两个无限字符串集合列出来，只要同时考虑两边当前所在的段，
 *      尝试上面的三种动作，就包含了所有可能的字符串和所有编辑方案。
 *
 * 关键性质：
 *   - 让一边的当前段单独结束时：
 *     普通字母一定会生成一次，只能将它删除或插入，代价为 $1$；
 *     `a?` 和 `a*` 都可以选择生成零个 `a`，所以可以用 $0$ 代价跳过。
 *   - 让两边各生成一个字母时：字母相同不花代价，不同就替换一次，代价为 $1$。
 *     普通字母和 `?` 最多生成一次，用过后必须进入下一段；
 *     `*` 还可以继续生成同一个字母，所以用过后仍停在当前段。
 *   - 每次有用的转移都会让 $i$ 或 $j$ 至少一个变大，绝不会回到更小的下标。
 *     唯一例外是两边当前都是 `*`：同时生成一次后两个下标都不变，
 *     但字母相同不会改善答案，字母不同反而增加代价，因此这种原地转移可以忽略。
 *     所以按 $i$、$j$ 从小到大枚举时，更新出的格子一定会在当前格之后被处理，不会漏算。
 *
 * 核心思路：
 *   1. 将两个表达式分别拆成 $n,m$ 段。设 $f[i][j]$ 表示已经结束 $A$ 的前 $i$ 段、
 *      $B$ 的前 $j$ 段时，已经产生的最小编辑代价，初始值为 $f[0][0]=0$。
 *
 *   2. 在每个 $f[i][j]$ 处尝试三种选择：
 *      让 $A$ 的下一段单独结束；让 $B$ 的下一段单独结束；让两边的下一段各生成一个字母。
 *      前两种选择分别对应删除和插入，第三种选择对应匹配或替换。
 *
 *   3. 两边的所有段都结束时，$f[n][m]$ 就已经比较了所有可生成字符串的配对，
 *      因而它就是题目要求的最小编辑距离。
 *
 * 时间复杂度：$\mathcal{O}(nm)$，空间复杂度：$\mathcal{O}(nm)$。
 */

int main() {
    // freopen("friend.in", "r", stdin);
    // freopen("friend.out", "w", stdout);

    cin >> a >> b;
    int n = Parse(a, 0), m = Parse(b, 1);

    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) {
                if (atoms[0][i + 1].ch2 == ' ') f[i + 1][j] = min(f[i + 1][j], f[i][j] + 1);
                else f[i + 1][j] = min(f[i + 1][j], f[i][j]);
            }
            if (j < m) {
                if (atoms[1][j + 1].ch2 == ' ') f[i][j + 1] = min(f[i][j + 1], f[i][j] + 1);
                else f[i][j + 1] = min(f[i][j + 1], f[i][j]);
            }
            if (i < n && j < m) {
                int ni = (atoms[0][i + 1].ch2 == '*') ? i : i + 1;
                int nj = (atoms[1][j + 1].ch2 == '*') ? j : j + 1;
                if (ni != i || nj != j) f[ni][nj] = min(f[ni][nj], f[i][j] + (atoms[0][i + 1].ch1 != atoms[1][j + 1].ch1));
            }
        }
    }

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

    return 0;
}