問題一覧 > 通常問題

No.874 正規表現間距離

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : kakira9618kakira9618 / テスター : pockynypockyny
4 ProblemId : 2776 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-08-15 23:23:35

問題文

? か * か 小文字のアルファベットからなる正規表現(のサブセット)の文字列 $A$, $B$ が与えられます。
ここで、? は1つ前の文字の0回もしくは1回の繰り返し、* は1つ前の文字の0回以上の繰り返しを表します。
$A$, $B$のそれぞれについて、その正規表現によって生成される文字列の集合を$G_A$, $G_B$とします。
例えば、$A = $ "a?b*"のとき、$G_A=\{$"", "a", "b", "ab", "bb", "abb", "bbb", "abbb", $\cdots \}$ です。

小文字アルファベットだけからなる文字列$a$と$b$について、$a$と$b$の 編集距離 $d(a, b)$を
「1文字の挿入・削除・置換によって、$a$を$b$に変形するのに必要な手順の最小回数」
と定めます。
例えば "abcdefgh"と"zcdefgha"の編集距離を考えると、 "abcdefgh" に対し、
aの削除、bのzへの置換、aの追加を行うことで "zcdefgha" に変形でき、
これが最小回数であるため、$d("$abcdefgh$", "$zcdefgha$") = 3$となります。

$A$、$B$に関する 正規表現間距離 $D(A, B)$ を $\min_{(a, b) \in G_A \times G_B } d(a, b)$ とします。
つまり、$D(A, B)$を「AとBそれぞれで生成されうる文字列の全ての組み合わせにおける編集距離の最小」と定義します。
このとき、$D(A, B)$ を求めてください。

入力

$A$
$B$

$A$, $B$ は ? か * か 小文字のアルファベットからなる文字列である。
? や * が$A$や$B$の中に連続して出現することはない ("??", "?*", "*?", "**"という文字列を連続部分文字列として含まない)。
$A$, $B$ の先頭文字が ? もしくは * であることはない。
$1 \leq |A| \leq 2000$
$1 \leq |B| \leq 2000$

出力

$D(A, B)$ を1行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
ab?c
abc
出力
0

$G_A = \{$ "ac", "abc" $\}$, $G_B = \{$ "abc" $\}$ です。
$d($"ac", "abc"$) = 1$, $d($"abc", "abc"$) = 0$ であるので、0を出力します。

サンプル2
入力
a*bcd
aaaabd?
出力
1

例えば、$a =$ "aaaabcd", $b =$ "aaaabd" とすると、編集距離が1となり、これが最小です。

サンプル3
入力
aaaaabbbaaaaa
a*b?c*
出力
3

"b?"の甘い誘惑を振り切り、$b =$ "aaaaaaaaaaaaa" とすると編集距離が3となり、最小となります。

サンプル4
入力
aaaaabbbaaaaa
a*b?a*
出力
2

"b?"の提案を受け入れ、$b =$ "aaaaaabaaaaaaa" とすると編集距離が2となり、最小となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。