염기서열 커버

생명 공학을 연구하는 현생이는 요즘 DNA 염기서열을 연구하고 있다. DNA 염기서열이란 4종류의 핵염기 a(아데닌), c(사이토신), g(구아닌), t(티민)이 일자로 연결된 가닥이다. 문자열로는 a, c, g, t 네 문자의 나열로 나타낸다.

현생이는 인간에게 좋게 작용하는 좋은 염기서열 N개를 가지고 있고 이 모든 좋은 염기서열의 길이는 M이다. 주어진 좋은 염기서열은 몇 개의 와일드 카드(.)을 가지고 있어, 이 부분에는 a, c, g, t의 어떤 염기가 들어가도 좋은 염기서열로 작용한다고 하자.