1071. Speech Patterns.md

【PAT A-1071】Speech Patterns

题意概述

找出给定的段落中出现次数最多的字符串，如果不唯一，输出字典序最小的字符串。

输入输出格式

输入只有一行字符串。

在一行中输出出现次数最多的字符串及其出现次数。

数据规模

字符串长度不超过 1048576。

算法设计

利用map<string,int>将字符串与出现次数对应起来，注意 map 会按键排序。用 cin 读取输入的字符串 si，这时读取的字符串会自动按空格符分隔。定义字符串 t=""，遍历该字符串 si 的每个字符，如果遇到字母或数字字符，将该字符加入 t 中；否则当前单词读取结束，如果 t 不为空，递增字符串 t 在 map 中出现的次数。注意遍历完字符串 si 后如果 t 不为空，还要再递增一次字符串 t 在 map 中出现的次数，因为最后一个单词并未统计到 map 中。统计完所有单词出现次数之后，遍历 map 找出出现次数最多的输出即可。

注意点

1. 只有字母和数字组合成的单词才是合法的，换句话说，单词之间以任意非字母和数字的字符分隔。
2. 不区分大小写。
3. 字符串按小写字母输出。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string si;
    map<string, gg> ans;
    while (cin >> si) {
        string t;
        for (char i : si) {
            if (isalnum(i)) {
                t.push_back(tolower(i));
            } else {
                if (not t.empty())
                    ++ans[t];
                t = "";
            }
        }
        if (not t.empty())
            ++ans[t];
    }
    auto res =
        max_element(ans.begin(), ans.end(),
                    [](const pair<string, gg>& p1, const pair<string, gg>& p2) {
                        return p1.second < p2.second;
                    });
    cout << res->first << " " << res->second;
    return 0;
}