C - 天下一文字列集合
Editorial
/ 
/ 
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
英小文字 (a～z) と、英小文字 1 文字と一致するワイルドカード (*) からなる m 文字の文字列のパターンが n 個与えられる。
この文字列のパターンは、 m 文字の英小文字からなる文字列の集合 X のいずれかの要素に一致するようにように作られたものである。
集合 X の要素数の最小値を求めよ、ダイキ君。
入力
入力は、以下の形式で標準入力から与えられる。
n m P1 P2 : Pn
1 行目に文字列のパターンの数を表す整数 n( 1 ≦ n ≦ 14 ) と文字列の長さを表す整数 m( 1 ≦ m ≦ 100000 ) が与えられる。 その後、長さ m の文字列のパターン P_i が n 行で与えられる。
部分点
- 1 ≦ n ≦ 4, 1 ≦ m ≦ 4 の全てのテストケースに正解した場合、部分点として20点が与えられる
- 1 ≦ n ≦ 14, 1 ≦ m ≦ 10 の全てのテストケースに正解した場合、部分点としてさらに30点が与えられる
出力
集合 X としてありうる要素数のうち最小の値を1行で出力せよ。 なお、行の終端には改行が必要である。
入力例1
5 4 a*x* *xx* *x*b **cb ****
出力例1
2
集合 X の例としては、
axxb oocb
がありうる。