7-44 基于词频的文件相似度（30 分）

题目内容

新浪微博可以在发言中嵌入“话题”，即将发言中的话题文字写在一对“#”之间，就可以生成话题链接，点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表，并将最热门的话题放在醒目的位置推荐大家关注。

本题目要求实现一个简化的热门话题推荐功能，从大量英文（因为中文分词处理比较麻烦）微博中解析出话题，找出被最多条微博提到的话题。

##输入格式:

输入说明：输入首先给出一个正整数N（≤105），随后N行，每行给出一条英文微博，其长度不超过140个字符。任何包含在一对最近的#中的内容均被认为是一个话题，输入保证#成对出现。

##输出格式:

第一行输出被最多条微博提到的话题，第二行输出其被提到的微博条数。如果这样的话题不唯一，则输出按字母序最小的话题，并在第三行输出And k more …，其中k是另外几条热门话题的条数。输入保证至少存在一条话题。

注意：两条话题被认为是相同的，如果在去掉所有非英文字母和数字的符号、并忽略大小写区别后，它们是相同的字符串；同时它们有完全相同的分词。输出时除首字母大写外，只保留小写英文字母和数字，并用一个空格分隔原文中的单词。

输入样例:

4
This is a #test of topic#.
Another #Test of topic.#
This is a #Hot# #Hot# topic
Another #hot!# #Hot# topic

输出样例:

Hot
2
And 1 more …

解题思路

1、读入每行的字符串之后，检索所有topic，并进行转换
2、topic转换的时候，注意首字母大写，其余字母小写，其他字符用空格替换，并注意单词末尾空格的删除
3、由于要统计提及热门话题对应的条数，但是同一条中可能多次重复热门话题，因此选择使用set来存储话题条数，最后使用set的size来比较大小。
4、由于map具有自动排序功能，因此次数可以默认存储字母序列较小的热门话题。

AC代码

#include<string>
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
using namespace std;
string change(string &s)
{
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        if((s[i]>='a'&&s[i]<='z') || (s[i]>='A'&&s[i]<='Z') || (s[i]>='0'&&s[i]<='9'))
        {
            if(i!=0 && (s[i]>='A'&&s[i]<='Z'))
                s[i]=s[i]-'A'+'a';
            if(i==0 && (s[i]>='a'&&s[i]<='z'))
                s[i]=s[i]-'a'+'A';
        }
        else{
            s.replace(i,1," ");
        }
    }
    if(s[len-1]==' ')
        s.erase(s.end()-1);
    return s;
}
int main()
{
    int N;
    scanf("%d",&N);
    map<string,set<int>> topic;
    string tmp;
    getchar();
    for(int i=0;i<N;i++){
        getline(cin,tmp,'\n');
        int cur=0,begin,end;
        string sub,h;
        while(cur!=string::npos){
            sub=tmp.substr(cur);
            if((begin=sub.find("#"))!=string::npos)
                sub=sub.substr(begin+1);
            else
                break;
            if((end=sub.find("#"))!=string::npos)
                h=sub.substr(0,end);
            else
                break;
            h=change(h);
            topic[h].insert(i);
            cur+=begin+end+2;
        }
    }
    int max=0,mct=0;
    string h;
    for(map<string,set<int>>::iterator it=topic.begin();it!=topic.end();it++)
    {
        if(it->second.size()>max){
            max=it->second.size();
            h=it->first;
            mct=1;
        }
        else if(it->second.size()==max){
            mct++;
            if(it->first<h)
                h=it->first;
        }
    }
    cout<<h<<endl;
    cout<<max<<endl;
    if(mct>1)
        cout<<"And "<<mct-1<<" more ..."<<endl;
    return 0;
}