얼룩말 유전자 timer 1s memory 128MB

정올이는 N마리의 얼룩말과 N마리의 일반말을 키우고 있다. 최근에 그는 말의 얼룩이 유전자 상의 특정 위치에서 발생하는 돌연변이 때문이라고 확신하게 되었다.

정올이는 많은 비용을 들여 말들의 유전체를 시퀀싱했다. 각 유전체는 A, C, G, T 네 개의 문자로 이루어진 길이 M의 문자열이다. 그리고 말들의 유전체를 정렬하면 아래와 같은 표를 얻을 수 있다. 예를 들어, N=3일 때는 다음과 같다:

위치:     1 2 3 4 5 6 7 ... M

얼룩말 1: A A T C C C A ... T

얼룩말 2: G A T T G C A ... A

얼룩말 3: G G T C G C A ... A

일반말 1: A C T C C C A ... G

일반말 2: A C T C G C A ... T

일반말 3: A C T T C C A ... T

이 표를 자세히 살펴본 정올이는 2번째 위치가 얼룩을 설명할 수 있는 잠재적인 위치라고 추측한다. 즉, 이 위치에서 나타나는 문자만 보고도 어떤 말이 얼룩이 있는지 없는지를 구별할 수 있다는 것이다. 예를 들어, 2번째 위치에서 A나 G는 얼룩말을 의미하고, C는 일반말을 의미한다. T는 이 위치에서는 나타나지 않으므로 무시할 수 있다. 첫 번째 위치는 자체적으로 얼룩을 설명할 수 없다. 왜냐하면 첫 번째 위치에서 A는 얼룩말일 수도, 일반말일 수도 있기 때문이다.

정올이는 말들의 유전체를 보고, 얼룩을 설명할 수 있는 위치가 몇 개인지 세고자 한다.