結果
| 問題 |
No.874 正規表現間距離
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 15:06:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,119 bytes |
| コンパイル時間 | 148 ms |
| コンパイル使用メモリ | 82,312 KB |
| 実行使用メモリ | 859,364 KB |
| 最終ジャッジ日時 | 2025-06-12 15:07:17 |
| 合計ジャッジ時間 | 9,292 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | AC * 1 WA * 26 MLE * 1 -- * 10 |
ソースコード
import sys
from collections import deque
def parse_regex(regex):
tokens = []
i = 0
while i < len(regex):
if regex[i] == '?' or regex[i] == '*':
quantifier = regex[i]
# Previous character must exist
prev_char = tokens[-1][0]
tokens[-1] = (prev_char, quantifier)
i += 1
else:
# Check if next character is quantifier
if i + 1 < len(regex) and (regex[i+1] == '?' or regex[i+1] == '*'):
quantifier = regex[i+1]
tokens.append((regex[i], quantifier))
i += 2
else:
tokens.append((regex[i], ''))
i += 1
return tokens
def main():
A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()
tokens_A = parse_regex(A)
tokens_B = parse_regex(B)
lenA = len(tokens_A)
lenB = len(tokens_B)
INF = float('inf')
dp = [ [ [ [INF] * 2 for _ in range(2) ] for __ in range(lenB + 1) ] for ___ in range(lenA + 1) ]
dp[0][0][0][0] = 0
dirs = []
for i in range(lenA + 1):
for j in range(lenB + 1):
for a_step in range(2):
for b_step in range(2):
if dp[i][j][a_step][b_step] == INF:
continue
current_cost = dp[i][j][a_step][b_step]
if i < lenA:
a_token = tokens_A[i]
a_char = a_token[0]
a_quant = a_token[1]
else:
a_quant = ''
if j < lenB:
b_token = tokens_B[j]
b_char = b_token[0]
b_quant = b_token[1]
else:
b_quant = ''
a_choices = []
if i < lenA:
if a_quant == '?':
if a_step == 0:
a_choices.append( (0, 0) ) # take 0, next i+1, a_step 0
a_choices.append( (1, 1) ) # take 1, next i+1, a_step 1
else:
a_choices.append( (0, 0) )
elif a_quant == '*':
if a_step == 0:
a_choices.append( (0, 0) )
a_choices.append( (1, 1) )
else:
a_choices.append( (1, 1) )
a_choices.append( (0, 0) )
else: # exact
a_choices.append( (1, 0) ) # take 1, next i+1, a_step 0
else:
a_choices.append( (0, 0) )
b_choices = []
if j < lenB:
if b_quant == '?':
if b_step == 0:
b_choices.append( (0, 0) )
b_choices.append( (1, 1) )
else:
b_choices.append( (0, 0) )
elif b_quant == '*':
if b_step == 0:
b_choices.append( (0, 0) )
b_choices.append( (1, 1) )
else:
b_choices.append( (1, 1) )
b_choices.append( (0, 0) )
else: # exact
b_choices.append( (1, 0) )
else:
b_choices.append( (0, 0) )
for a_choice, new_a_step in a_choices:
for b_choice, new_b_step in b_choices:
if a_choice == 1 and i >= lenA:
continue
if b_choice == 1 and j >= lenB:
continue
if a_choice == 1:
a_char = tokens_A[i][0]
else:
a_char = None
if b_choice == 1:
b_char = tokens_B[j][0]
else:
b_char = None
cost = 0
if a_choice == 0 and b_choice == 0:
pass # cost 0
elif a_choice == 0 and b_choice == 1:
cost = 1
elif a_choice == 1 and b_choice == 0:
cost = 1
else:
if a_char != b_char:
cost = 1
new_i = i
new_j = j
if a_choice == 1:
if a_quant == 'exact' or a_quant == '?' or (a_quant == '*' and new_a_step == 0):
new_i += 1
if b_choice == 1:
if b_quant == 'exact' or b_quant == '?' or (b_quant == '*' and new_b_step == 0):
new_j += 1
if a_quant == '*' and a_choice == 1 and new_a_step == 1:
new_a_step = 1
new_i = i
else:
new_a_step = 0
if b_quant == '*' and b_choice == 1 and new_b_step == 1:
new_b_step = 1
new_j = j
else:
new_b_step = 0
if a_choice == 1 and a_quant == '?' and new_a_step == 1:
new_i += 1
new_a_step = 0
if b_choice == 1 and b_quant == '?' and new_b_step == 1:
new_j += 1
new_b_step = 0
if a_choice == 1 and a_quant == '*' and new_a_step == 0:
new_i += 1
if b_choice == 1 and b_quant == '*' and new_b_step == 0:
new_j += 1
new_cost = current_cost + cost
if new_i > lenA or new_j > lenB:
continue
if new_cost < dp[new_i][new_j][new_a_step][new_b_step]:
dp[new_i][new_j][new_a_step][new_b_step] = new_cost
min_distance = INF
for a_step in range(2):
for b_step in range(2):
if dp[lenA][lenB][a_step][b_step] < min_distance:
min_distance = dp[lenA][lenB][a_step][b_step]
print(min_distance)
if __name__ == "__main__":
main()