PAT甲级真题1071 Speech Patterns 【字符串处理】题解

绝地灬酷狼 2021-07-24 22:25 294阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

不同  
的人对描述同一种事物的同义词的偏爱程度可能不同。

例如，在说警察时，有人喜欢用 the police，有人喜欢用 the cops。

分析说话方式有助于确定说话者的身份，这在验证诸如和你线上聊天的是否是同一个人十分有用。

现在，给定一段从某人讲话中提取的文字，你能确定他的最常用词吗？

**输入格式**  
输入共一行，包含一个字符串，以回车符 \\n 终止。  
**输出格式**  
共一行，输出最常用词以及其出现次数。

如果常用词有多个，则输出字典序最小的那个单词。

注意，单词在输出时，必须全部小写。

单词是指由连续的字母和数字构成的，被非字母数字字符或行首/行尾分隔开的，连续序列。

单词不区分大小写。  
**数据范围**  
输入字符串长度不超过 1048576，且至少包含一个大小写字母或数字。  
**输入样例：**  
`Can1: "Can a can can a can? It can!"`  
**输出样例：**  
`can 5`

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<unordered_map>
    using namespace std;
    bool check(char c)  //检验字符的合法性
    { 
        if(c>='0'&&c<='9') return true;
        if(c>='a'&&c<='z') return true;
        if(c>='A'&&c<='Z') return true;
        return false;
    }
    char to_lower(char c) //大写的字符转换成小写的
    { 
        if (c>='A'&&c<='Z')  c+=32;
        return c;
    }
    int main()
    { 
        string str;
        getline(cin,str);  //读取一行
        unordered_map<string,int>hash;   //建立映射
        for(int i=0;i<str.size();i++)
        { 
            int j=i;      //双指针算法
            if(check(str[i]))
            { 
                string word;
                while(j<str.size()&&check(str[j]))
                { 
                    word+=to_lower(str[j]);
                    j++;
                }
                i=j;
                hash[word]++;
            }
        }
        string word;
        int cnt=-1;
        for(auto c: hash)
        { 
           if(c.second>cnt||c.second==cnt&&c.first<word)
           { 
               word=c.first;
               cnt=c.second;
           }
        }
        cout<<word<<' '<<cnt<<endl;
        return 0;
    }