正規表現の積

誰か解いて

追記ここから

（長さの制約は適当なのでもっと大きくしても解けるなら大きくしてもらって構わない。）

— %20（物理的身近に人がいない） (@henkoudekimasu) 2017年3月5日

一応言っておくと、自力で解けないから「誰か解いて」と言ったのであって、だから想定解なんかは知らないし、テストケースを持ってるわけでもないよ。

— %20（物理的身近に人がいない） (@henkoudekimasu) 2017年3月5日

時間制限: 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 と表せる。