1022. Digital Library (30)

A Digital Library contains millions of books, stored according to their titles, authors, key Words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID's.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:

It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.

After the book information, there is a line containing a positive integer M (<=1000) which is the number of user's search queries. Then M lines follow, each in one of the formats shown below:

Output Specification:

For each query, first print the original query in a line, then output the resulting book ID's in increasing order, each occupying a line. If no book is found, print "Not Found" instead.

Sample Input:

31111111The Testing BookYue Chentest code debug sort keywordsZUCS Print20113333333Another Testing BookYue Chentest code sort keywordsZUCS Print220122222222The Testing BookCYLLkeywords debug bookZUCS Print2201161: The Testing Book2: Yue Chen3: keywords4: ZUCS Print5: 20113: blablabla

Sample Output:

1: The Testing Book111111122222222: Yue Chen111111133333333: keywords1111111222222233333334: ZUCS Print11111115: 2011111111122222223: blablablaNot Found

#include<cstdio>#include<iostream>#include<string>#include<algorithm>#include<vector>#include<map>using namespace std;typedef int book;int ID[10001];map<string,vector<book> > mf;//核心數據結構，一個關鍵詞對應一個book指針數組 void FindAnswer(string s){ if(mf.find(s)!=mf.end()){  sort(mf[s].begin(),mf[s].end());//我選擇最后排序  for(int i=0;i!=mf[s].size();i++)  printf("%07d/n",mf[s][i]); } else cout<<"Not Found"<<endl;}void BuildMap(string s,int i){ vector<book> empty; if(mf.find(s)==mf.end())  mf.insert(pair<string,vector<book> >(s,empty));  mf[s].push_back(ID[i]);}int main(){ int N,i,j,M; string t,search; cin>>N; for(i=0;i<N;i++){//輸入并建立哈希表   cin>>ID[i];  cin.get();  for(j=0;j<5;j++){   char c=' ';   string s;   if(j!=2){//keyword部分需要單獨考慮，其他的部分其實都是一樣的     getline(cin,s);    BuildMap(s,i);   }   else{    while(c!='/n'){     c=cin.get();    if(c!='/n'&&c!=' ')     s+=c;    else if(c==' '){     BuildMap(s,i);     s.clear();      }    }    BuildMap(s,i);   }  } } cin>>M; while(M--){  cin>>t;  cin.get();//去除上一個cin留下的回車符號   cout<<t<<" ";  getline(cin,search);  cout<<search<<endl;  FindAnswer(search);  search.clear(); }}