시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB39221445.161%

문제

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 以下である.

예제 입력 1

5
ATATATGCCCAT
ATAT
ATG
GCCC
GCCCAT
CAT

예제 출력 1

4

同じ素 DNA 鎖を何度も使って良いことに注意せよ.

예제 입력 2

1
AAAAAAAAAA
AAA

예제 출력 2

5

AAA を 2 つ用いて,AAAA と AAAAA のどちらも合成することができる.

예제 입력 3

2
ATATATATAT
ATA
TAT

예제 출력 3

5