POJ 2408 Anagram Groups：哈希分組 + 排序輸出前 5 大字母重組群組

題目要求

讀入所有單字（至 EOF），將「字母組成相同」（anagram）的單字分為一組。輸出群組大小前 5 大的群組，每組內按字典序輸出不重複單字。群組大小相同時，字典序最小單字較小的群組優先。

核心思路：特徵值哈希分組

對每個單字統計 26 個字母出現次數，構造唯一鍵值。單字長度 ≤ 30，頻率 ≤ 30，可用 64 位整數編碼：

using ULL = unsigned long long;
const int BASE = 31;  // > 30 確保無進位衝突

ULL hashKey(const char* s) {
    int cnt[26] = {0};
    for (int i = 0; s[i]; ++i) ++cnt[s[i]-'a'];
    ULL key = 0;
    for (int i = 0; i < 26; ++i) key = key * BASE + cnt[i];
    return key;
}

BASE=31 保證每個字母計數佔據獨立「位」，等價於 31 進制數，完美無衝突。

演算法流程

1. 讀入所有單字存入 words[]，計算哈希鍵存入 vector>（鍵、索引）。
2. 對向量按鍵排序，相同鍵連續 → 自然分組。
3. 掃描排序後向量，建立群組：
    記錄群組大小、群組代表單字（字典序最小）、成員索引列表。
4. 對群組按 (size 降序, 代表單字 升序) 排序。
5. 輸出前 5 群組：成員索引按單字字典序排序、去重後輸出。

完整 C++ 實作

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 30005;
const int MAXL = 30;
const int BASE = 31;
using ULL = unsigned long long;

char word[MAXN][MAXL];
char repWord[MAXN];  // 群組代表單字（字典序最小）
vector groupMembers[MAXN];
vector> vec;  // (hash, index)
vector> groups; // (groupId, size)

ULL hashKey(const char* s) {
    int cnt[26] = {0};
    for (int i = 0; s[i]; ++i) ++cnt[s[i]-'a'];
    ULL key = 0;
    for (int i = 0; i < 26; ++i) key = key * BASE + cnt[i];
    return key;
}

bool cmpGroup(const pair& a, const pair& b) {
    if (a.second != b.second) return a.second > b.second; // size 降序
    return strcmp(repWord[a.first], repWord[b.first]) < 0; // 代表單字 升序
}

bool cmpWordIdx(int a, int b) {
    return strcmp(word[a], word[b]) < 0;
}

int main() {
    int N = 0;
    while (scanf("%s", word[N]) == 1) {
        ULL key = hashKey(word[N]);
        vec.emplace_back(key, N);
        ++N;
    }
    sort(vec.begin(), vec.end(), [](auto& a, auto& b){ return a.first < b.first; });

    int gCnt = 0;
    ULL prevKey = ULL(-1);
    for (auto& p : vec) {
        int idx = p.second;
        if (p.first != prevKey) {
            if (gCnt > 0) groups.emplace_back(gCnt, (int)groupMembers[gCnt].size());
            prevKey = p.first;
            groupMembers[gCnt].clear();
            strcpy(repWord[gCnt], word[idx]);
            ++gCnt;
        }
        groupMembers[gCnt-1].push_back(idx);
        if (strcmp(word[idx], repWord[gCnt-1]) < 0)
            strcpy(repWord[gCnt-1], word[idx]);
    }
    if (gCnt > 0) groups.emplace_back(gCnt-1, (int)groupMembers[gCnt-1].size());

    sort(groups.begin(), groups.end(), cmpGroup);

    int outputCnt = min(5, (int)groups.size());
    for (int i = 0; i < outputCnt; ++i) {
        int gid = groups[i].first;
        printf("Group of size %d: ", groups[i].second);
        sort(groupMembers[gid].begin(), groupMembers[gid].end(), cmpWordIdx);
        for (int j = 0; j < groupMembers[gid].size(); ++j) {
            if (j == 0 || strcmp(word[groupMembers[gid][j-1]], word[groupMembers[gid][j]]) != 0)
                printf("%s ", word[groupMembers[gid][j]]);
        }
        printf(".\n");
    }
    return 0;
}

關鍵技術細節

• 哈希無衝突：BASE=31 > 最大頻率 30，每字母計數獨立編碼，理論上零衝突。
• 群組代表單字：分組時同步維護字典序最小單字，作為 tie-break 鍵。
• 輸出去重：同群組內可能有重複單字（輸入含重複），排序後相鄰比較去重。
• 記憶體優化：groupMembers 以索引儲存，避免複製字串。

複雜度分析

• 讀入與哈希：O(N × L)，L ≤ 30。
• 排序單字：O(N log N)。
• 分組掃描：O(N)。
• 群組排序：O(G log G)，G ≤ N。
• 組內排序輸出：總和 O(N log N)。
• 整體 O(N log N)，N ≤ 30000 極快。