Searching Quickly
Time limit: 3.000 seconds
Background
Searching and sorting are part of the theory and practice of computer science. For example, binary search provides a good example of an easy-to-understand algorithm with sub-linear complexity. Quicksort is an efficient[average case] comparison based sort.
KWIC-indexing is an indexing method that permits efficient “human search” of, for example, a list of titles.
The Problem
Given a list of titles and a list of “words to ignore”, you are to write a program that generates a KWIC (Key Word In Context) index of the titles. In a KWIC-index, a title is listed once for each keyword that occurs in the title. The KWIC-index is alphabetized by keyword.
Any word that is not one of the “words to ignore” is a potential keyword.
For example, if words to ignore are “the, of, and, as, a” and the list of titles is:
Descent of ManThe Ascent of ManThe Old Man and The SeaA Portrait of The Artist As a Young Man
A KWIC-index of these titles might be given by:
a portrait of the ARTIST as a young manthe ASCENT of manDESCENT of mandescent of MANthe ascent of MANthe old MAN and the seaa portrait of the artist as a young MANthe OLD man and the seaa PORTRAIT of the artist as a young manthe old man and the SEAa portrait of the artist as a YOUNG man
The Input
The input is a sequence of lines, the string::is used to separate the list of words to ignore from the list of titles. Each of the words to ignore appears in lower-case letters on a line by itself and is no more than 10 characters in length. Each title appears on a line by itself and may consist of mixed-case (upper and lower) letters. Words in a title are separated by whitespace. No title contains more than 15 words.
There will be no more than 50 words to ignore, no more than than 200 titles, and no more than 10,000 characters in the titles and words to ignore combined. No characters other than ‘a’-‘z’, ‘A’-‘Z’, and white space will appear in the input.
The Output
The output should be a KWIC-index of the titles, with each title appearing once for each keyword in the title, and with the KWIC-index alphabetized by keyword. If a word appears more than once in a title, each instance is a potential keyword.
The keyword should appear in all upper-case letters. All other words in a title should be in lower-case letters. Titles in the KWIC-index with the same keyword should appear in the same order as they appeared in the input file. In the case where multiple instances of a word are keywords in the same title, the keywords should be capitalized in left-to-right order.
Case (upper or lower) is irrelevant when determining if a word is to be ignored.
The titles in the KWIC-index need NOT be justified or aligned by keyword, all titles may be listed left-justified.
Sample Input
istheofandasabut::Descent of ManThe Ascent of ManThe Old Man and The SeaA Portrait of The Artist As a Young ManA Man is a Man but Bubblesort IS A DOG
Sample Output
a portrait of the ARTIST as a young man the ASCENT of man a man is a man but BUBBLESORT is a dog DESCENT of man a man is a man but bubblesort is a DOG descent of MAN the ascent of MAN the old MAN and the sea a portrait of the artist as a young MAN a MAN is a man but bubblesort is a dog a man is a MAN but bubblesort is a dog the OLD man and the sea a PORTRAIT of the artist as a young man the old man and the SEA a portrait of the artist as a YOUNG man
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<ctype.h>#define MAXN 400char title[204][MAXN];char keyword[52][14]; typedef struct charter{rank; start, end; // 这个单词在title中的位置 }charter;charter mes[3004];int dealenter(char *temp){len = strlen(temp);) temp[len-1] = ‘ ‘;;return 0;}int calculate(int n1, int n2, int n3){ i, j, k, flag;charter temp;for(i=0; i<n3-1; ++i){flag = 1;for(j=0; j<n3-1-i; ++j){if(strcmp(mes[j].character, mes[j+1].character) > 0){flag = 0;temp = mes[j], mes[j] = mes[j+1], mes[j+1] = temp;}}if(flag) break;}return 0;}int shuai(int n1, char *from){i, j, flag = 0;for(i=0; i<n1; ++i){if(strcmp(keyword[i], from) == 0) {flag = 1; break;}}return flag;}int lastline(int n1, int n2, int n3){ i, j, k, t, flag, len, start, end;for(i=0; i<n3; ++i){if(!shuai(n1, mes[i].character)){j = mes[i].rank;start = mes[i].start, end = mes[i].end;for(t=0; t<start; ++t)printf(, title[j][t]);len = strlen(mes[i].character);for(k=0; k<len; ++k)printf(, mes[i].character[k] – (- ));len = strlen(title[j]);for(k=end+1; k<len; ++k)printf(, title[j][k]);printf();}}}int main(){int i, j, t, k, n, m, count, cnt3, cnt1, cnt2, cnt4, flag, flag2, len, doc;char temp[MAXN];flag = cnt1 = cnt2 = cnt3 = 0;while(fgets(temp, MAXN, stdin) != NULL){dealenter(temp);len = strlen(temp);) == 0) flag = 1;else if(!flag){// 存储 ignore-words strcpy(keyword[cnt1], temp);keyword[cnt1++][len-;}else{(i=0,flag2=cnt4=0,doc=-1; i<len; ++i){if(temp[i] != ‘ ‘){if(doc == -1) doc = i;if(isupper(temp[i])) mes[cnt3].character[cnt4++] = temp[i] = towlower(temp[i]);else mes[cnt3].character[cnt4++] = temp[i];flag2 = 1;}else if(flag2){mes[cnt3].rank = cnt2, mes[cnt3].start = doc, mes[cnt3].end = i-1;mes[cnt3].character[cnt4] = ;cnt3++, cnt4 = 0;flag2 = 0, doc = -1;}}strcpy(title[cnt2], temp);title[cnt2++][len-;}}calculate(cnt1, cnt2, cnt3);lastline(cnt1, cnt2, cnt3);return 0;}
解题报告：
Runtime Error X 2 [据其原因是最后忘了加 return 0 ！！！ 果然，美国服务器，有很长时间没做题了]
看题目找思路，我的做法比较愚笨：
首先需要将ignore-word 和 titles[换成lowcase后的character] 用数组存储起来
然后在title中做文章，将每个单词从中分割出来，网站空间，需要存储的信息是这个单词属于哪一title，并存储title中所在的位置[下标表示]
将取出的单词进行按字典顺序排序
筛掉需要忽略掉的单词
对每个剩下的单词，网站空间，根据已存储的其他关于此单词的信息，找到所属的title，分三部分按题目要求样式输出
测试数据提供：
不必在乎目的地，在乎的是沿途的风景以及看风景的心情，让心灵去旅行！
