cho.sh

색인 생성

시간 제한1초메모리 제한128 MB

문제

대부분의 비소설·참고 서적에는 본문에서 특정 용어나 개념이 언급된 위치를 독자가 찾을 수 있도록 색인(index)이 실려 있습니다. 아래는 색인의 예입니다.

larch, 4, 237, 238, 414
+ Monty Python and, 64, 65, 66
+ planting of, 17
Lenny Kravitz, 50
+ going his way, 53
lumbago, 107
mango
+ Chris Kattan, 380
+ storage of, 87, 90
+ use in Nethack, 500, 501
+ Vitamin C content, 192

각 색인 항목은 하나의 주 항목(primary entry)과 그 뒤에 오는 0개 이상의 부 항목(secondary entry)으로 이루어지며, 부 항목은 모두 +로 시작합니다. 항목 뒤에는 보통 쪽 번호 목록이 이어지지만, 주 항목에 부 항목이 하나라도 있으면(위의 mango처럼) 주 항목 자체에는 쪽 번호가 없을 수 있습니다. 주 항목들은 정렬되며, 한 주 항목에 딸린 부 항목들도 정렬됩니다. 정렬은 대소문자를 구분하지 않습니다. 한 항목의 쪽 번호는 오름차순으로 나열되고 중복은 없습니다. (같은 쪽에 동일한 항목이 둘 이상 있으면 중복이 생길 수 있습니다.)

여러분의 과제는 색인 정보가 삽입된 문서를 읽어 색인을 만드는 것입니다. 문서는 한 줄 이상의 ASCII 텍스트로 이루어집니다. 쪽 번호는 1에서 시작하며, 문자 &는 새 쪽의 시작을 나타냅니다(현재 쪽 번호에 1을 더합니다). 색인 항목은 마커(marker)로 표시합니다. 가장 완전한 형태의 마커는 다음과 같은 구문을 가집니다.

{text%primary$secondary}

여기서 text는 색인에 넣을 텍스트, primary는 대체 주 항목, secondary는 부 항목입니다. %primary와 $secondary는 모두 선택 사항이지만, 둘 다 있는 경우에는 위에 보인 순서대로 나와야 합니다. primary가 있으면 그것이 주 항목으로 쓰이고, 없으면 text가 주 항목으로 쓰입니다. secondary가 있으면 마커는 그 부 항목에 대한 쪽 번호를 추가하고, 없으면 주 항목에 대한 쪽 번호를 추가합니다. 하나의 마커가 주 항목과 부 항목 양쪽에 동시에 쪽 번호를 추가할 수는 없습니다. 위 예시 색인의 네 항목에 대응하는, 가능한 네 가지 마커 유형의 예는 다음과 같습니다.

  • ... his {lumbago} was acting up, so ...
  • ... {Lenny%Lenny Kravitz} lit up the crowd with his version of ...
  • ... Monty Python often used the {larch$Monty Python and} in ...
  • ... when storing {mangos%mango$storage of}, be sure to ...

입력

입력은 하나 이상의 문서로 이루어지며, 마지막에는 오직 **만 있는 줄이 와서 입력의 끝을 나타냅니다. 문서는 1부터 차례로 암묵적으로 번호가 매겨집니다. 각 문서는 한 줄 이상의 텍스트와, 그 뒤에 오직 *만 있는 줄로 이루어집니다. 각 텍스트 줄은 줄 끝 문자를 제외하고 최대 79자입니다.

출력

문서 i에 대해, DOCUMENT i 줄을 출력한 뒤 정렬된 색인을 예제 테스트에 보인 것과 정확히 같은 형식으로 출력합니다.

힌트

다음에 유의하세요.

  • 한 문서에는 마커가 최대 100개, 주 항목이 최대 20개 있습니다.
  • 한 주 항목에는 부 항목이 최대 5개 있습니다.
  • 한 항목의 서로 다른 쪽 번호는 최대 10개입니다(중복은 세지 않습니다).
  • 문자 &는 마커 안에는 절대 나타나지 않으며, 한 문서에서 최대 500번 나타납니다.
  • 문자 *는 문서의 끝 또는 입력의 끝을 나타낼 때에만 쓰입니다.
  • 문자 {, }, %, $는 마커를 정의할 때에만 쓰이며, 일반 텍스트나 항목 안에는 나타나지 않습니다.
  • 마커는 한 줄 이상에 걸칠 수 있습니다. 마커 안의 모든 줄 끝은 하나의 공백으로 바뀝니다.
  • 마커 안의 공백(줄 끝이 바뀐 공백 포함)은 보통 다른 문자와 마찬가지로 텍스트/항목의 일부로 포함됩니다. 단, { 바로 뒤, } 바로 앞, 또는 %나 $에 바로 인접한 공백은 무시됩니다.
  • 여는 {부터 닫는 }까지(마커 안의 모든 줄 끝을 공백으로 바꾼 상태로) 측정한 마커의 전체 길이는 최대 79자입니다.