SRM392 Div2 500

問題

2つの文字列s1,s2が与えられる。各文字列はいくつかのアルファベットと1つの"*"を含む。
このアスタリスクを何らかの(長さ0以上の)文字列に置き換え、s1とs2を等しくしたい。
そのような文字列を作れた場合、最小の長さの文字列を返す。不可能な場合は"impossible"と返す。

考え方

2つの文字列はそれぞれそこに含まれている文字以外は使われないので、s1の"*"の部分にs2の部分文字列を入れてできた文字列s3がs2の"*"に適当に文字列をいれて作れるかどうかを調べた。

反省

両方の"*"の部分を2つの長さが合うように"?"などに置き換えて、両方の文字列から補完して作ればよい。