| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 230 | Accepted: 89 |
Description
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
Output
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
/*
Name: Shangli_Cloud
Copyright: Shangli_Cloud
Author: Shangli_Cloud
Date: 10/10/14 08:15
Description:
字符串处理题，
在读取过程中，遇到’&'就PAGe++；
我们要处理的对象为{}，
对象有 primary,secondary,page属性,所以结构体存储。
当遇到'{'是增加entry，遇标记，处理。
排序，三个因素。
我们遇标记处理，定义一个next_token（）标记函数，
定义一个next_char()函数为next_token()函数服务。
注意，当我们遇到某些字符时，需要读取下一个字符，之后再用next_char()的会又会
读取下一个字符，这个字符就跳过了。
所以增加一个变量 lookahead表示是否是有效字符的开始。
*/
#include"iostream"
#include"cstdio"
#include"cstring"
#include"string"
#include"algorithm"
#include"set"
#include"map"
#include"stack"
#include"queue"
#include"vector"
#include"cstdlib"
#include"ctime"
using namespace std;
const int EndOfDocument=-;
const int EndOfFile=-;
char ch;
char token;
int page;
bool lookahead;
struct Entry
{
string primary;
string secondary;
int page;
Entry(string p,string s):primary(p),secondary(s),page(::page){};
} ;
vector<Entry> entry;
int string_compare(const string &s,const string &t)
{
int m=s.length();
int n=t.length();
int k=m<n?m:n;
for(int i=;i<k;i++)
{
int a=toupper(s[i]);
int b=toupper(t[i]);
if(a!=b)
return a-b;
}
return m==n?:m<n?-:;
}
bool less_than(const Entry &s,const Entry &t)
{
int cmp=string_compare(s.primary,t.primary);
if(cmp<)
return true;
if(cmp>)
return false;
cmp=string_compare(s.secondary,t.secondary);
if(cmp<)
return true;
if(cmp>)
return false;
return s.page<t.page;
}
inline char next_char()
{
if(lookahead)
lookahead=false;
else
ch=cin.get();
return ch;
} char next_token ()
{
switch (next_char ())
{
case '*':
token = (next_char () == '*') ? EndOfFile : EndOfDocument;
break;
case ' ':
case '\n':
next_char ();
if (ch == '%' || ch == '$' || ch == '}')
token = ch;
else {
token = ' ';
lookahead = true;
break;
}
case '{': case '%': case '$':
token = ch;
lookahead = ! isspace (next_char ());
break;
default:
token = ch;
}
return token;
} inline bool is_delimiter(char t)
{
return t=='%'||t=='$'||t=='}';
} void add_entry ()
{
string primary, secondary;
while (! is_delimiter (next_token ()))
primary += token;
if (token == '%')
{
primary.erase (); //primary="";
while (! is_delimiter (next_token ()))
primary += token;
}
if (token == '$')
while (! is_delimiter (next_token ()))
secondary += token;
entry.push_back (Entry (primary, secondary));
} int main ()
{
for (int document = ; ; ++document)
{
if (next_token () == EndOfFile) break;
cout << "DOCUMENT " << document;
page = ;
entry.clear ();
entry.push_back (Entry ("", ""));
//cout<<"----"<<entry.size()<<endl;
do {
if (token == '&')
++page;
else if (token == '{')
add_entry ();
} while (next_token () != EndOfDocument);
sort (entry.begin (), entry.end (), less_than);
for (int i = ; i < entry.size(); ++i)
{
if (entry[i].primary == entry[i-].primary)
if (entry[i].secondary == entry[i-].secondary)
{
if (entry[i].page != entry[i-].page)
cout << ", " << entry[i].page;
}
else
cout<<"\n+ "<<entry[i].secondary<<", "<<entry[i].page;
else
{
cout << '\n' << entry[i].primary;
if (entry[i].secondary == "")
cout << ", " << entry[i].page;
else
cout<<"\n+ "<<entry[i].secondary<<", "<<entry[i].page;
}
}
cout << endl;
}
return ;
}