KINA Is Not Abbreviation

여러 단어로 이루어진 새로운 용어를 소개할 때는 약어를 쓰면 편리하다. 약어란 연속한 몇 개의 단어의 첫 글자를 모아 만든 단어이다.

약어가 다음 두 조건을 모두 만족하면 명확하다고 한다.

• 본문에서 정확히 하나의 단어 나열에만 대응한다(그 단어 나열이 본문에 여러 번 나타나도 상관없다);
• 그 약어 자체가 본문에 단독으로 나타나지 않는다.

예를 들어 본문 A recursive acronym KINA means "KINA is not abbreviation"에서 ARA와 K는 명확한 약어이고, A와 KINA는 명확하지 않은 약어이며, RAA와 KNA는 약어가 아니다.

약어를 도입하려면 그 약어가 대응하는 단어 나열 바로 뒤에 괄호로 감싸 적는다. 그 뒤로 같은 단어 나열이 다시 나타나면 약어로 바꿀 수 있다. 위 본문에 약어 K를 도입하면 A recursive acronym KINA (K) means "K is not abbreviation"가 된다.

같은 단어 나열의 두 출현이 겹치면 그중 하나만 약어로 바꿀 수 있다. 단어들은 하나 이상의 비알파벳 문자로 구분되며, 글자는 대소문자를 구분하지 않고 비교한다. 예를 들어 i18n은 단어 나열 I n의 한 출현이다.

약어의 효율은 그 약어를 도입한 뒤 줄어드는 글자 수이다. 글자만 세며 공백, 괄호, 그 밖의 모든 비알파벳 문자는 세지 않는다.

본문이 주어질 때, 효율이 가장 큰 명확한 약어를 찾아라.

입력은 최대 4000자의 본문이다. ASCII 코드 32(공백)부터 126(~)까지의 문자와 13(캐리지 리턴), 10(라인 피드)만 포함한다.

효율이 양수인 명확한 약어가 없으면 0 한 줄만 출력한다.

그렇지 않으면 두 줄을 출력한다. 첫 줄에는 최대 효율을 출력한다. 둘째 줄에는 약어 자체를 대문자로 출력한다. 최대 효율을 내는 명확한 약어가 여러 개이면 대문자 문자열 기준 사전순으로 가장 앞선 것을 출력한다.

k개 단어로 이루어진 약어는 연속한 k개 단어로 된 구간이며, 그 글자는 각 단어의 첫 글자이다. 글자는 대소문자를 구분하지 않으므로 Jingle bells와 jingle bells는 같은 단어 나열이다.

사전순 우선 규칙 덕분에 답이 유일해진다. not abbreviation이라는 구가 반복되는 본문에서는 NA와 INA가 모두 최대 효율에 도달할 수 있는데, INA가 NA보다 사전순으로 앞서므로 INA를 출력한다.