C - シークエンサー
Editorial
/ 
/ 
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
A,T,G,Cのいずれかの文字と任意の 1 文字にマッチするワイルドカード(.)からなる文字列のパターンが N 個与えられる。
1 つのパターンには最大で 1 個のワイルドカードが含まれる。
与えられたパターン全てを部分文字列として含む文字列 X のうち最も短いものの長さを答えよ、ヨシオ君。
入力
入力は以下の形式で標準入力から与えられる。
N S1 S2 : SN
- 1行目には、パターンの数 N(1 \leq N \leq 12) が与えられる。
- 2行目から N 行には、i番目のパターン Si が与えられる。
- Si の長さ |Si| は 1 \leq |Si| \leq 600 を満たす。
- Si はA,T,G,Cのいずれかの文字またはワイルドカード (.) からなる。
- Si に含まれるワイルドカードの数は最大 1 文字である。
部分点
- 与えられたパターン全てにワイルドカードが含まれないケースに正解した場合、部分点として 60 点を与える。
出力
最短の文字列 X の長さを 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
2 TAG GAT
出力例1
5
最短の文字列 X は TAGATまたはGATAGです。
入力例2
4 AA. TAT ATTAC. TA.T
出力例2
9
最短の文字列 X は AATTACTAT です。