24114번 - DNA の合成 (DNA synthesizer) 다국어

문제

A,T,G,C からなる DNA 鎖が 2 本あるとき, 一方の先頭と, 他方の末尾の部分に 1 文字以上の連続する共通 部分を持つものをつなげて新しい DNA 鎖を合成する方法が開発された. このとき共通部分は一つにまとめ られる. たとえば,TTTATGC と ATGCAAA は,前者の末尾と後者の先頭に共通部分 ATGC を持つので,つ なげて TTTATGCAAA を合成できる. また,AAA を 2 つ用いて,AAAA と AAAAA のどちらも合成するこ とができる.今,新薬開発のために,研究室にあるいくつかの素 DNA 鎖から,ある DNA 鎖を合成したい.

研究室には N 種類の素 DNA 鎖がある.上記の方法で素 DNA 鎖をつなぎあわせて目的の DNA 鎖を合成 するとき, 最小で何本の素 DNA 鎖が必要となるかを求めるプログラムを作成せよ. ただし,素 DNA 鎖の備 蓄には余裕があるので,同じ種類の素 DNA 鎖を何度でも使うことができる.また,全ての採点データにお いて,目的の DNA 鎖を得る素 DNA 鎖の組み合わせが存在する.

입력

標準入力から以下の入力を読み込め.

• 1 行目には整数 N が書かれている.
• 2 行目には,A,T,G,C からなる文字列が書かれており, 目的の DNA 鎖を表す.
• 続く N 行は,1 行につき 1 つの A,T,G,C からなる文字列が書かれており,それぞれ 1 つの素 DNA 鎖 を表す.重複する素 DNA 鎖は存在しない.

출력

標準出力に必要となる素 DNA の本数の最小値を表す 1 つの整数を出力せよ.

제한

• 素 DNA 鎖の種類数 N は 50,000 以下である.
• 合成したい DNA 鎖の長さは 150,000 以下である.
• 素 DNA 鎖の長さは 20 以下である.

힌트