优化单词搜索程序时间复杂度：PC^2提交遇TLE问题求助

你的程序超时的核心原因是文本单词匹配时的线性遍历：每次从文本中提取一个单词，都要遍历整个目标单词数组（for (size_t i = 0; i < dic_actual_num; ++i)）。如果目标单词数量多（比如几千个），再加上长文本，时间复杂度会达到O(M*N)（M是文本单词数，N是目标单词数），这肯定会触发超时。

下面是具体的优化思路和修改方案：

1. 用二分查找替换线性遍历（快速实现，无需额外库） #

先把目标单词数组按字典序排序，然后用C标准库的bsearch函数进行二分查找，查找时间复杂度从O(N)降到O(logN)，整体时间复杂度变为O(M logN)，能大幅提升速度。

修改步骤： #

• 定义结构体绑定单词和计数，避免排序后计数和单词对应关系混乱
• 读取完目标单词后，用qsort对结构体数组排序
• 处理文本单词时，用bsearch快速定位目标单词

示例代码片段：

// 定义结构体绑定单词与计数
typedef struct {
    char* word;
    int count;
} WordCount;

WordCount* dic;
int dic_actual_num = 0;
int dic_assume_num = 1000;

int main() {
    // 初始化结构体数组
    dic = malloc(dic_assume_num * sizeof(WordCount));
    char divider[6] = "-----";
    ssize_t bytes_read;
    size_t nbytes = 2047;
    char* my_string = malloc((nbytes + 1) * sizeof(char));

    // 读取目标单词
    while ((bytes_read = getline(&my_string, &nbytes, stdin)) != -1) {
        my_string[strcspn(my_string, "\n")] = '\0';
        if (strncmp(my_string, divider, 5) == 0) {
            break;
        } else {
            dic[dic_actual_num].word = strdup(my_string);
            dic[dic_actual_num].count = 0;
            dic_actual_num++;
            // 扩容逻辑
            if (dic_actual_num >= dic_assume_num) {
                dic_assume_num *= 2;
                dic = realloc(dic, dic_assume_num * sizeof(WordCount));
            }
        }
    }

    // 按字典序排序目标单词
    qsort(dic, dic_actual_num, sizeof(WordCount), 
        (const void* a, const void* b) {
            return strcmp(((WordCount*)a)->word, ((WordCount*)b)->word);
        });

    // 处理文本单词
    char tmp[2048];
    while (1) {
        // 跳过非有效字符
        int c;
        while ((c = getchar()) != EOF && !((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'));
        if (c == EOF) break;
        ungetc(c, stdin);
        // 读取有效单词
        if (scanf("%2047[a-zA-Z0-9_]", tmp) != 1) break;
        
        // 二分查找匹配
        WordCount key = {.word = tmp};
        WordCount* found = bsearch(&key, dic, dic_actual_num, sizeof(WordCount),
            (const void* a, const void* b) {
                return strcmp(((WordCount*)a)->word, ((WordCount*)b)->word);
            });
        if (found != NULL) {
            found->count++;
        }
    }

    // 输出结果（已排序，直接遍历）
    for (int i = 0; i < dic_actual_num; i++) {
        printf("%s %d ", dic[i].word, dic[i].count);
        free(dic[i].word);
    }

    // 内存释放
    free(dic);
    free(my_string);
    return 0;
}

2. 用哈希表进一步提速（最优性能） #

如果OJ环境支持第三方库（比如uthash），或者你自己实现简单哈希表，查找时间复杂度可以降到O(1)平均情况，这是性能最优的方案。

用uthash的示例： #

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

// 哈希表结构体
typedef struct {
    char* word;
    int count;
    UT_hash_handle hh; // utash哈希句柄
} HashTable;

HashTable* hash_table = NULL;

// 插入目标单词到哈希表
void add_target_word(char* word) {
    HashTable* entry;
    HASH_FIND_STR(hash_table, word, entry);
    if (entry == NULL) {
        entry = malloc(sizeof(HashTable));
        entry->word = strdup(word);
        entry->count = 0;
        HASH_ADD_STR(hash_table, word, entry);
    }
}

// 统计文本单词
void count_text_word(char* word) {
    HashTable* entry;
    HASH_FIND_STR(hash_table, word, entry);
    if (entry != NULL) {
        entry->count++;
    }
}

// 哈希表排序规则（按strcmp顺序）
int sort_by_word(const void* a, const void* b) {
    return strcmp(((HashTable*)a)->word, ((HashTable*)b)->word);
}

int main() {
    char divider[6] = "-----";
    ssize_t bytes_read;
    size_t nbytes = 2047;
    char* my_string = malloc((nbytes + 1) * sizeof(char));

    // 读取目标单词存入哈希表
    while ((bytes_read = getline(&my_string, &nbytes, stdin)) != -1) {
        my_string[strcspn(my_string, "\n")] = '\0';
        if (strncmp(my_string, divider, 5) == 0) {
            break;
        } else {
            add_target_word(my_string);
        }
    }

    // 处理文本
    char tmp[2048];
    while (1) {
        int c;
        while ((c = getchar()) != EOF && !((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'));
        if (c == EOF) break;
        ungetc(c, stdin);
        if (scanf("%2047[a-zA-Z0-9_]", tmp) != 1) break;
        count_text_word(tmp);
    }

    // 排序并输出结果
    HASH_SORT(hash_table, sort_by_word);
    HashTable *current, *tmp_entry;
    HASH_ITER(hh, hash_table, current, tmp_entry) {
        printf("%s %d ", current->word, current->count);
        HASH_DEL(hash_table, current);
        free(current->word);
        free(current);
    }

    free(my_string);
    return 0;
}

3. 优化输入处理效率 #

原来的多次scanf调用会有IO开销，换成getline读取整行后在内存中分割单词，能减少IO调用次数：

// 处理文本部分替换为整行读取
char* text_line = malloc(1025 * sizeof(char));
size_t text_len = 1024;
while ((bytes_read = getline(&text_line, &text_len, stdin)) != -1) {
    char* ptr = text_line;
    while (*ptr != '\0') {
        // 跳过非有效字符
        while (*ptr != '\0' && !(((*ptr >= 'a' && *ptr <= 'z') || (*ptr >= 'A' && *ptr <= 'Z') || (*ptr >= '0' && *ptr <= '9') || *ptr == '_'))) {
            ptr++;
        }
        if (*ptr == '\0') break;
        // 提取单词
        char* start = ptr;
        while (*ptr != '\0' && ((*ptr >= 'a' && *ptr <= 'z') || (*ptr >= 'A' && *ptr <= 'Z') || (*ptr >= '0' && *ptr <= '9') || *ptr == '_')) {
            ptr++;
        }
        int word_len = ptr - start;
        strncpy(tmp, start, word_len);
        tmp[word_len] = '\0';
        // 调用计数函数
        count_text_word(tmp);
    }
}
free(text_line);

额外注意点 #

• 保持原有的内存翻倍扩容策略，避免频繁扩容带来的开销
• 输出时确保按strcmp顺序：二分查找的数组已排序，哈希表需要先排序再输出
• 如果题目要求不区分大小写，可在读取单词时统一转为小写再处理

内容的提问来源于stack exchange，提问作者LINPOHSIEN