PAT 1071 Speech Patterns：單詞頻統計找最高頻詞（忽略大小寫）

題目大意

輸入一行文本（≤ 1048576 字符），統計「單詞」出現次數。單詞定義：字母數字序列（[0-9A-Za-z]），非字母數字分隔。忽略大小寫。輸出最高頻單詞（小寫）及其次數，並列時輸出字典序最小者。

解法：單遍歷 + 哈希表統計

• 逐字符讀入，字母數字轉小寫累積成單詞
• 遇到分隔符或行尾，單詞結束，map[word]++
• 最後遍歷 map 找最大值，並列取最小鍵

C++ 代碼

#include 
using namespace std;
int main() {
    map cnt;
    string word;
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF) {
        if (isalnum(ch)) word += tolower(ch);
        else if (!word.empty()) { cnt[word]++; word.clear(); }
    }
    if (!word.empty()) cnt[word]++;
    
    string best; int maxc = 0;
    for (auto& [w, c] : cnt) {
        if (c > maxc || (c == maxc && w < best)) {
            maxc = c; best = w;
        }
    }
    cout << best << ' ' << maxc << endl;
    return 0;
}

關鍵點

1. isalnum + tolower：標準庫函數處理字符分類與大小寫
2. map 自動有序：遍歷時並列鍵天然按字典序，簡化並列邏輯
3. 超長行：getchar() 逐字符讀取避免緩衝區限制
4. 行尾處理：循環結束後檢查 word 是否非空

Sample 驗證

Input: Can1: "Can a can can a can? It can!"
單詞：can1, can, a, can, can, a, can, it, can
統計：can→5, a→2, can1→1, it→1
Output: can 5 ✓