読者です 読者をやめる 読者になる 読者になる

37.50.48

%20 の ブログ

正規表現の積

誰か解いて

追記ここから

時間制限: 2秒 / メモリ制限: 512MB

追記ここまで

問題文

[a-z.] のみから成る2つの正規表現 A, B が与えられる。
A, B に共にマッチするような文字列の集合全体を、[a-z.*|] のみから成る正規表現 C で表したい。
このとき、C に含まれる | の個数の最小値を答えよ。

入力
A
B

入力は以下の制約を満たす。

  • 1 ≦ |A|, |B| ≦ 10
  • A, B には、[a-z.] 以外の文字は含まれない。
サンプル

入力1

a
b

出力1

1

C を例えば a.*b|b.*a と表した場合、| の個数は1で、これが最小値である。

入力2

a.a
.b.

出力2

2

例えば aba|a.a.*b.|.b.*a.a と表せる。

入力3

.a.b
a.b.

出力3

2

例えば aabb|.a.b.|a.b.*a.b と表せる。

入力4

b.a.
.a.b

出力4

5

例えば baab|.abba.|b.a.b|.a.b.a.|b.a.*a.b|.a.b.*b.a. と表せる。
追記:赤で示した部分が抜けていたので追加した。それに伴い出力4を修正した。

入力5

confused
sed

出力5

0

例えば confused と表せる。