화성 DNA

러시아는 우주 탐사 분야에서 성과를 거둔 것으로 알려져 있다. 최근 러시아 과학자들이 화성 토양 샘플을 분석하다가 DNA일 가능성이 있다고 보는 이상한 분자를 발견했다. 이 분자는 일반 DNA의 네 가지 염기 대신 두 가지 염기만 가진다. 따라서 분자 전체를 0과 1로 이루어진 문자열로 나타낼 수 있다.

과학자들은 이 분자의 길이를 측정했고, 분자는 $n$개의 염기 원소로 이루어져 있다. 이제 DNA 원소를 부호화한 0과 1의 문자열 $S$, 즉 이 분자의 구조를 알아내려 한다. 이를 위해 특수한 DNA 분석기에서 테스트를 실행할 수 있다. 각 테스트에서 문자열 $P$로 부호화한 원소 배열을 입력하면, 분석기는 $P$가 분자에 나타나는지, 즉 $P$가 $S$의 부분 문자열인지 확인한다. 샘플이 매우 약하므로 과학자들이 할 수 있는 테스트는 $t$회뿐이다. DNA 서열의 구조를 알아내도록 올바른 테스트를 설계하는 일을 도와 달라.