結果

問題 No.874 正規表現間距離
ユーザー lam6er
提出日時 2025-04-16 00:10:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,234 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 131,792 KB
最終ジャッジ日時 2025-04-16 00:12:02
合計ジャッジ時間 4,194 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 15 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def parse_regex(s):
    elements = []
    i = 0
    while i < len(s):
        char = s[i]
        if i + 1 < len(s) and s[i+1] in ('?', '*'):
            op = s[i+1]
            elements.append((char, op))
            i += 2
        else:
            elements.append((char, None))
            i += 1
    return elements

def compute_cost(a_elem, b_elem):
    a_char, a_op = a_elem
    b_char, b_op = b_elem
    if a_char == b_char:
        a_forced_one = (a_op is None)
        b_forced_one = (b_op is None)
        if a_forced_one and b_forced_one:
            return 0
        a_can_zero = a_op in ('?', '*')
        b_can_zero = b_op in ('?', '*')
        if a_can_zero or b_can_zero:
            return 0
        else:
            return 0
    else:
        a_can_zero = a_op in ('?', '*')
        b_can_zero = b_op in ('?', '*')
        if a_can_zero and b_can_zero:
            return 0
        a_min = 0 if a_can_zero else 1
        b_min = 0 if b_can_zero else 1
        if a_can_zero and b_can_zero:
            return 0
        elif a_can_zero:
            return max(0, b_min)
        elif b_can_zero:
            return max(a_min, 0)
        else:
            return max(a_min, b_min)

a = input().strip()
b = input().strip()

a_elems = parse_regex(a)
b_elems = parse_regex(b)

len_a = len(a_elems)
len_b = len(b_elems)

INF = float('inf')
dp = [[INF] * (len_b + 1) for _ in range(len_a + 1)]
dp[0][0] = 0

for i in range(len_a + 1):
    for j in range(len_b + 1):
        if dp[i][j] == INF:
            continue
        # Process both elements
        if i < len_a and j < len_b:
            cost = compute_cost(a_elems[i], b_elems[j])
            if dp[i+1][j+1] > dp[i][j] + cost:
                dp[i+1][j+1] = dp[i][j] + cost
        # Skip A's element (delete)
        if i < len_a:
            a_op = a_elems[i][1] if i < len_a else None
            if a_op in ('?', '*'):
                if dp[i+1][j] > dp[i][j]:
                    dp[i+1][j] = dp[i][j]
        # Skip B's element (insert)
        if j < len_b:
            b_op = b_elems[j][1] if j < len_b else None
            if b_op in ('?', '*'):
                if dp[i][j+1] > dp[i][j]:
                    dp[i][j+1] = dp[i][j]

print(dp[len_a][len_b])
0