DNA 주입

작년에 소나무좀(Dendroctonus ponderosae)이 이 지역의 숲을 황폐화시켰다. Debbie는 소나무좀을 연구하던 중 큰 과학적 발견을 해냈다!

인간의 DNA는 네 가지 주요 염기인 아데닌(A), 사이토신(C), 구아닌(G), 티민(T)으로 이루어져 있다. 소나무좀의 DNA는 스물여섯 가지 주요 염기로 이루어져 있으며, 이는 알파벳 대문자로 나타낸다. DNA 가닥은 염기의 나열이며, 대응하는 문자들의 문자열로 나타낼 수 있다. Debbie가 해낸 놀라운 발견은, 어떤 소나무좀 DNA 가닥을 인간 DNA에 주입하면 인간이 감기에 면역이 된다는 것이다!

안타깝게도 단점이 하나 있다. 소나무좀의 DNA는 인간에게 다소 독성이 있다. 몇 달간 연구한 끝에 Debbie는 DNA 가닥의 독성이 그 가닥의 접미사들과 관련이 있다는 결론을 내렸다(비어 있지 않은 접미사만 고려한다). 먼저 그 가닥의 모든 접미사를 사전 순으로 정렬해야 한다. 두 접미사가 순서를 벗어났다는 것은, 이 정렬 순서에서 더 긴 접미사가 더 짧은 접미사보다 앞에 나오는 경우를 말한다. 어떤 가닥의 독성은 순서를 벗어난 (순서 없는) 접미사 쌍의 수보다 1만큼 크다. 예를 들어, 다음과 같은 소나무좀 DNA 가닥을 보자: BUBBLE. 이 가닥의 접미사를 정렬하면 다음과 같다:

BBLE BLE BUBBLE E LE UBBLE

순서를 벗어난 접미사 쌍이 여덟 개 있으므로 BUBBLE의 독성은 9 (8 + 1)이다. 순서를 벗어난 접미사 쌍은 (BLE, E), (BLE, LE), (BBLE, E), (BBLE, LE), (BBLE, BLE), (BUBBLE, E), (BUBBLE, LE), (BUBBLE, UBBLE)이다.

가닥이 길수록 감기와 더 잘 싸우므로 이는 절충 관계이다. Debbie는 DNA 가닥의 효능에 대한 공식을 만들어 냈다. 길이가 n인 DNA 가닥 S에 대해:

• toxicity(S) ≤ 108이면 effectiveness(S) = n(n-1)/toxicity(S)
• 그렇지 않으면 effectiveness(S) = 0

Debbie는 소나무좀 DNA 한 조각을 추출했고, 이 가닥의 어떤 접미사든 감기와 싸울 수 있다는 것을 알아냈다. Debbie가 가닥의 어떤 접미사가 효능이 가장 높은지 결정할 수 있도록 도와주자. 효능이 같은 접미사가 여러 개라면 더 긴 것을 고른다.

입력은 Debbie가 고른 DNA 가닥인 하나의 문자열을 포함하는 한 줄로 이루어진다. 문자열은 대문자만을 포함하며 길이는 1 이상 200 000 이하이다.

Debbie가 고를 DNA 가닥의 길이를 출력한다.