유전자 접기

국제 세포 처리 회사(ICPC)는 유전 서열 분석 분야의 세계적 선두 주자다. 유전 서열은 뉴클레오티드의 나열이며, 이 문제에서는 A, C, G, T 네 글자만으로 이루어진 문자열로 표현한다. 각 글자는 각각 Adenine, Cytosine, Guanine, Thymine을 나타낸다.

ICPC가 발견한 중요한 사실 중 하나는, Genetically Optimized Organic Folding(GOOF)이라는 과정을 거치면 유전 서열을 더 단순한 서열로 바꿀 수 있다는 것이다. 이때 ICPC가 분석하려는 서열의 여러 성질은 그대로 유지된다.

GOOF를 한 번 적용하는 방법은 다음과 같다. 뉴클레오티드 서열에서 인접한 두 뉴클레오티드 사이의 한 지점을 찾는데, 그 지점에서 양쪽 방향으로 읽었을 때 가까운 쪽 끝까지의 서열이 같아야 한다. 예를 들어 서열 ATTACC에는 이런 지점이 두 개 있다: AT-TACC와 ATTAC-C. 이 중 한 지점을 고르고(예를 들어 첫 번째 지점), 그 지점에서 유전자 서열을 접어서 동일한 뉴클레오티드를 합친다(이 경우 AT와 TA가 합쳐져 결과 서열은 CCAT 또는 TACC가 된다).

GOOF를 반복해서 적용하면 뉴클레오티드 서열을 훨씬 짧게 만들 수 있다. 하지만 적절한 접는 지점을 일일이 찾는 것은 매우 오래 걸린다. ICPC는 접는 지점을 자동으로 찾고, 주어진 입력 서열로부터 가장 짧은 유전자 서열을 얻도록 지점을 선택하는 프로그램을 작성해 달라고 요청했다.

입력은 분석할 뉴클레오티드 서열을 나타내는 문자열 s 하나로 이루어진다. 문자열은 A, C, G, T 문자로만 구성된다. s의 길이는 1 이상 4 · 106 이하다.

GOOF를 0번 이상 적용해 입력으로부터 얻을 수 있는 서열 길이의 최솟값을 출력한다.