問題概要

大規模な動物名リストから最も頻繁に出現する動物名とその出現回数を出力する問題です。入力される動物名はすべて小文字アルファベットで構成され、文字列長は10文字以内に制限されています。

入力仕様

• 1行目：動物名の数 N (1 ≤ N ≤ 4,000,000)
• 2行目以降：N個の動物名（各文字列は小文字アルファベットのみ）

出力仕様

最も出現回数の多い動物名とその回数をスペース区切りで出力（同率1位は存在しないことが保証されています）

サンプル実行例

入力

10
boar
pig
sheep
gazelle
sheep
sheep
alpaca
alpaca
marmot
mole

出力

sheep 3

辞書木による実装

大規模な文字列データの頻度カウントには辞書木（Trie木）が効果的です。各ノードが文字に対応し、文字列の終端でカウントを保持します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TrieNode {
    int frequency;
    struct TrieNode *children[26];
} Trie;

int register_animal(char name[], Trie *root);
char* find_most_frequent(Trie *root, char buffer[]);

int main() {
    int animal_count;
    scanf("%d", &animal_count);
    
    Trie *root = (Trie*)malloc(sizeof(Trie));
    root->frequency = 0;
    for(int i = 0; i < 26; i++) {
        root->children[i] = NULL;
    }
    
    char current_name[12], top_animal[12];
    int max_count = 0;
    
    for(int i = 0; i < animal_count; i++) {
        scanf("%s", current_name);
        int count = register_animal(current_name, root);
        if(count > max_count) {
            max_count = count;
            strcpy(top_animal, current_name);
        }
    }
    
    printf("%s %d\n", top_animal, max_count);
    return 0;
}

int register_animal(char name[], Trie *node) {
    int length = strlen(name);
    for(int i = 0; i < length; i++) {
        int index = name[i] - 'a';
        if(node->children[index] == NULL) {
            Trie *new_node = (Trie*)malloc(sizeof(Trie));
            new_node->frequency = 0;
            for(int j = 0; j < 26; j++) {
                new_node->children[j] = NULL;
            }
            node->children[index] = new_node;
        }
        node = node->children[index];
    }
    node->frequency++;
    return node->frequency;
}

この実装では、各文字ごとにノードをたどり、文字列終端でカウントをインクリメントします。新しい文字が出現するたびに動的にノードを確保することで、メモリ効率よく大規模データを処理できます。