H - Hello, Xmas Contest 2018
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
やっぱりクリスマスには看板が欠かせませんし,不思議な看板の読み方をするうなぎも欠かせません.
問題文
うさぎが Xmas Contest 2018 に向けて看板を作ろうとしている.看板はマス目が長方形のグリッド状に並んだもので,それぞれのマスには 1 文字だけ文字を書くことができる.文字を書かないマスがあっても構わない.
うさぎが書ける文字の種類は,英大文字 (A-Z
),飾りの星マーク (*
) のいずれかである.
うなぎが看板を読むときには,以下のようにして看板から文字列を読みとる:
- 上の行から順に 1 行ずつ見ていく.
- それぞれの行に対し,その行のいずれのマスにも文字が書かれていなければ,その行は無視する.
- その行に文字の書かれているマスがあれば,そのうち最も左のマスに書かれている文字を読みとる.
うさぎは,うなぎが看板を読んだときに読みとる文字列から星マーク (*
) を除いたものがちょうど文字列 S となるように看板を作ろうとしている.
それだけでなく,もし看板の行と列を反転させたとしたときに,うなぎが看板を読んだときに読みとる文字列から星マーク (*
) を除いたものがちょうど文字列 T となるようにしたいと考えている.
うさぎは,文字を書くインクが節約できるとうれしいので,上記の条件を満たすような看板を作るときに文字を書く必要があるマスの個数の最小値を求めることにした.
制約
- 1 \le |S| \le 50.
- 1 \le |T| \le 50.
- S, T は英アルファベット大文字のみからなる.
入力
S T
出力
問題文の条件を満たすような看板を作るときに文字を書く必要があるマスの個数の最小値を出力せよ.ただし,そのような看板を作ることが不可能な場合は,代わりに -1 を出力せよ.
入力例 1
USAGI UNAGI
出力例 1
6
例えば以下のように文字を書けばよい.
入力例 2
WA AC
出力例 2
4
例えば以下のように文字を書けばよい.
マス目のサイズに制限はないという点に注意せよ.