Index Generation

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 230		Accepted: 89

Description

Most nonfiction and reference books have an index to help readers find references to specific terms or concepts in the text. Here is a sample 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

Each index entry contains a primary entry followed by zero or more secondary entries, which begin with a '+'. Entries will normally be followed by a list of page references, but a primary entry might not be if at least one secondary entry is present (as is the case with mango, above). Primary entries are sorted, and secondary entries following a primary entry are also sorted. Sorting is case-insensitive. Page references for an entry are in ascending order and do not include duplicates. (A duplicate could occur if there are two or more identical entries on the same page.)

Your task is to read a document that has index information embedded within it and produce the index. Documents consist of one or more lines of ASCII text. The page number starts at 1, and the character '&' indicates the start of a new page (which adds 1 to the current page number). Index entries are indicated by a marker, which in its most elaborate form has the following syntax:

{text%primary$secondary}
Here text is the text to be indexed, primary is an alternative primary entry, and secondary is a secondary entry. Both '%primary' and '$secondary' are optional, but if both are present they must appear in the order given. If primary is present then it is used as the primary entry, and if not then text is used as the primary entry. If secondary is present then the marker adds a page reference for that secondary entry; otherwise it adds a page reference for the primary entry. A single marker cannot add a page reference for both a primary and secondary entry. Here are examples of each of the four possible types of marker, which correspond to four of the entries in the sample index above.

... 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 ...

Input

The input consists of one or more documents, followed by a line containing only '**' that signals the end of the input. Documents are implictly numbered starting with 1. Each document consists of one or more lines of text followed by a line containing only '*'. Each line of text will be at most 79 characters long, not counting end-of-line characters. For document i, output the line 'DOCUMENT i' followed by the sorted index using the exact output format shown in the examples.

Output

Note:

A document will contain at most 100 markers, with at most 20 primary entries.
A primary entry will have at most 5 secondary entries.
An entry will have at most 10 unique page references (not including duplicates).
The character '&' will not appear anywhere within a marker, and will appear at most 500 times within a document.
The character '*' is used only to signal the end of a document or the end of the input.
The characters '{', '}', '%', and '$' will only be used to define markers, and will not appear in any text or entries.
A marker may span one or more lines. Every end-of-line within a marker must be converted to a single space.
A space within a marker (including a converted end-of-line) is normally included in the text/entry, just like any other character. However, any space that immediately follows '{', immediately precedes '}', or is immediately adjacent to '%' or '$' must be ignored.
The total length of a marker, measured from the opening '{' to the closing '}', and in which all embedded end-of-lines are converted to spaces, will be at most 79 characters.

Sample Input

Call me Ishmael.
*
One {fish $unary}, two {fish$ binary},&red {fish $ scarlet}, blue {fish$
azure}. & By { Dr. Seuss }.
*
This is a {simple } & & { document} that &{
simply %simple
$adverb
} & {illustrates %vision} &&&&& one {simple-minded% simple} {Judge}'s {vision} 
for what a {document } might { look % vision} like.
*
**

Sample Output

DOCUMENT 1
DOCUMENT 2
Dr. Seuss, 3
fish
+ azure, 2
+ binary, 1
+ scarlet, 2
+ unary, 1
DOCUMENT 3
document, 3, 10
Judge, 10
simple, 1, 10
+ adverb, 4
vision, 5, 10

  1 /*
  2     Name: Shangli_Cloud
  3     Copyright: Shangli_Cloud
  4     Author: Shangli_Cloud
  5     Date: 10/10/14 08:15
  6     Description: 
  7     字符串处理题，
  8     在读取过程中，遇到’&'就PAGe++； 
  9     我们要处理的对象为{}，
 10     对象有  primary,secondary,page属性,所以结构体存储。
 11     当遇到'{'是增加entry，遇标记，处理。
 12     排序，三个因素。
 13     我们遇标记处理，定义一个next_token（）标记函数，
 14     定义一个next_char()函数为next_token()函数服务。
 15     注意，当我们遇到某些字符时，需要读取下一个字符，之后再用next_char()的会又会
 16     读取下一个字符，这个字符就跳过了。
 17     所以增加一个变量  lookahead表示是否是有效字符的开始。 
 18 */
 19 #include"iostream"
 20 #include"cstdio"
 21 #include"cstring"
 22 #include"string"
 23 #include"algorithm"
 24 #include"set"
 25 #include"map"
 26 #include"stack"
 27 #include"queue"
 28 #include"vector"
 29 #include"cstdlib"
 30 #include"ctime"
 31 using namespace std;
 32 const int EndOfDocument=-1;
 33 const int EndOfFile=-2;
 34 char ch;
 35 char token;
 36 int page;
 37 bool lookahead;
 38 struct Entry
 39 {
 40     string primary;
 41     string secondary;
 42     int page;
 43     Entry(string p,string s):primary(p),secondary(s),page(::page){};
 44 } ;
 45 vector<Entry>  entry;
 46 int string_compare(const string &s,const string &t)
 47 {
 48     int m=s.length();
 49     int n=t.length();
 50     int k=m<n?m:n;
 51     for(int i=0;i<k;i++)
 52     {
 53         int a=toupper(s[i]);
 54         int b=toupper(t[i]);
 55         if(a!=b)
 56             return a-b;
 57     }
 58     return m==n?0:m<n?-1:1;
 59 }
 60 bool less_than(const Entry &s,const Entry &t)
 61 {
 62     int cmp=string_compare(s.primary,t.primary);
 63     if(cmp<0)
 64         return true;
 65     if(cmp>0)
 66         return false;
 67     cmp=string_compare(s.secondary,t.secondary);
 68     if(cmp<0)
 69         return true;
 70     if(cmp>0)
 71         return false;
 72     return s.page<t.page;
 73 }
 74 inline char next_char()
 75 {
 76     if(lookahead)
 77         lookahead=false;
 78     else
 79         ch=cin.get();
 80     return ch;
 81 }
 82 
 83 
 84 char next_token ()
 85 {
 86     switch (next_char ())
 87     {
 88     case '*':
 89         token = (next_char () == '*') ? EndOfFile : EndOfDocument;
 90         break;
 91     case ' ': 
 92     case '
':
 93         next_char ();
 94         if (ch == '%' || ch == '$' || ch == '}')
 95             token = ch;
 96         else {
 97             token = ' ';
 98             lookahead = true;
 99             break;
100     }
101     case '{': case '%': case '$':
102         token = ch;
103         lookahead = ! isspace (next_char ());
104         break;
105     default:
106         token = ch;
107     }
108     return token;
109 }
110 
111 
112 inline bool is_delimiter(char t)
113 {
114     return t=='%'||t=='$'||t=='}';
115 }
116 
117 
118 void add_entry ()
119 {
120     string primary, secondary;
121     while (! is_delimiter (next_token ()))
122         primary += token;
123     if (token == '%')
124     {
125         primary.erase ();  //primary="";
126         while (! is_delimiter (next_token ()))
127             primary += token;          
128     }
129     if (token == '$')
130         while (! is_delimiter (next_token ()))
131             secondary += token;
132     entry.push_back (Entry (primary, secondary));
133 }
134 
135 
136 int main ()
137 {
138     for (int document = 1; ; ++document)
139     {
140         if (next_token () == EndOfFile) break;
141         cout << "DOCUMENT " << document;
142         page = 1;
143         entry.clear ();
144         entry.push_back (Entry ("", ""));
145         //cout<<"----"<<entry.size()<<endl;
146         do {
147             if (token == '&')
148                 ++page;
149             else if (token == '{')
150                 add_entry ();
151         } while (next_token () != EndOfDocument);
152         sort (entry.begin (), entry.end (), less_than);
153         for (int i = 1; i < entry.size(); ++i)
154         {
155             if (entry[i].primary == entry[i-1].primary)
156                 if (entry[i].secondary == entry[i-1].secondary)
157                 {
158                     if (entry[i].page != entry[i-1].page)
159                         cout << ", " << entry[i].page;
160                 }
161                 else
162                     cout<<"
+ "<<entry[i].secondary<<", "<<entry[i].page; 
163             else
164             {
165                 cout << '
' << entry[i].primary;
166                 if (entry[i].secondary == "")
167                     cout << ", " << entry[i].page;
168                 else
169                     cout<<"
+ "<<entry[i].secondary<<", "<<entry[i].page;
170             }
171         }
172         cout << endl;
173     }
174     return 0;
175 }