首页 > 基础算法 > 字符串处理 > hdu 1623 Searching Quickly-字符串处理-[解题报告]
2013
12-16

hdu 1623 Searching Quickly-字符串处理-[解题报告]

Searching Quickly

问题描述 :

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 O(nlongn) [average case] comparison based sort.

KWIC-indexing is an indexing method that permits efficient “human search” of, for example, a list of titles.

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 Man
The Ascent of Man
The Old Man and The Sea
A 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 man 
                                    the ASCENT of man 
                                        DESCENT of man 
                             descent of MAN 
                          the ascent of MAN 
                                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 
                    the old man and the SEA 
          a portrait of the artist as a YOUNG man

输入:

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

样例输入:

is
the
of
and
as
a
but
::
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 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

AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume
1. Elementary Problem Solving
 ::Sorting/Searching


Description

在一些文章标题中, 寻找关键词。

所谓关键词, 就是在一个过滤词表中, 没有被过滤掉的单词。

请将关键词找出来后, 按字典序排序。

且输出关键词时, 是将关键词在标题中以全大写的形式出现(其他单词全变为小写),

然后输出整个句子。


Type

Sorting/Searching


Analysis

利用 STL map 做起来就容易了,

将关键词作键, 对应的句子作值, 储存于 multimap 中。

(由于可能出现相同的关键词, 所以应该用 multimap)

连字典序排序都剩了。


最后要注意, 标题和过滤词表在输入时可以全转为小写,

会比较方便字符串操作。


Solution

// UVaOJ 123
// Searching Quickly
// by A Code Rabbit

#include <cctype>
#include <iostream>
#include <set>
#include <string>
#include <map>
using namespace std;

string word;
string title;

string ToLower(string str);
string ToUpper(string str);

int main() {
    set<string> words;
    while (getline(cin, word)) {
        if (word == "::") break;
        else words.insert(ToLower(word));
    }

    multimap<string, string> kwic;
    while (getline(cin, title)) {
        title = ToLower(title);
        string key;
        string val = title;
        for (int i = 0; i <= title.length(); i++) {
            if ((i == title.length() || title[i] == ' ') && key != "") {
                if (!words.count(key)) {
                    key = ToUpper(key);
                    for (int j = 0; j < key.length(); j++)
                        val[i - key.length() + j] = key[j];
                    kwic.insert(make_pair(key, val));
                    val = title;
                }
                key = "";
            } else {
                key += title[i];
            }
        }
    }

    for (map<string, string>::iterator iter = kwic.begin();
        iter != kwic.end();
        ++iter)
    {
        cout << iter->second << endl;
    }
    

    return 0;
}

string ToLower(string str) {
    for (int i = 0; i < str.length(); i++)
        str[i] = tolower(str[i]);
    return str;
}

string ToUpper(string str) {
    for (int i = 0; i < str.length(); i++)
        str[i] = toupper(str[i]);
    return str;
}

解题转自:http://blog.csdn.net/ra_winding/article/details/8207202