이노폴리스의 생명

\mathbb{INNOPOLIS} \~ \mathbb{TIMES}

2016년 12월 18일

이노폴리스에 생명이 있는가?

이노폴리스의 생명은 우주에서 온 물체가 가져왔을지도 모른다. 한 과학자가 이 지역에서 채취한 물의 성분을 조사한 끝에 내린 결론이다. 이상한 DNA 구조가 그를 흥미롭게 했다. 연구에는 수년이 걸릴 것이다...

연구를 앞당기기 위해 그가 당신을 찾아왔다. DNA를 네 가지 염기 A, C, G, T에 대응하는 네 개의 대문자로 이루어진 문자열 $s$로 나타내자. 과학자의 질문은 하나뿐이다. 몇 개의 위치 $i$에서 위치 $i$부터 시작하는 접미사가 위치 $i + 1$부터 시작하는 접미사보다 사전순으로 작은가?

접미사는 문자열의 마지막 문자로 끝나는 연속한 문자의 나열이다. 문자열 자체도 자기 자신의 접미사이다. 예를 들어 ACGC, CGC, GC, C는 모두 문자열 ACGC의 접미사이다.

문자열 $a$가 문자열 $b$보다 사전순으로 작다는 것은, $a$와 $b$의 처음 $k$개 문자가 같고 $a_{k+1} < b_{k+1}$인 $k$가 존재하거나, $a$가 $b$보다 짧으면서 모든 $i \le |a|$에 대해 $a_i = b_i$라는 뜻이다. 예를 들어 "A" < "G", "AAG" < "AAT", "AGC" < "AGCA"이다.

입력은 라틴 알파벳 대문자 A, C, G, T로만 이루어진 문자열 $s$ 하나로 주어진다.

문자열의 길이는 $3\,000\,000$을 넘지 않는다.

위치 $i$부터 시작하는 접미사가 위치 $i + 1$부터 시작하는 접미사보다 사전순으로 작은 위치 $i$의 개수를 정수 하나로 출력한다.

첫 번째 예제에는 그러한 위치가 세 개 있다.

1. $i=1$: "ACGACA" < "CGACA"
2. $i=2$: "CGACA" < "GACA"
3. $i=4$: "ACA" < "CA"

두 번째 예제에는 두 개뿐이다.

1. $i=1$: "AATTAA" < "ATTAA"
2. $i=2$: "ATTAA" < "TTAA"