算法竞赛“读题”自动化？手把手教你用C语言写个简易题目过滤器（灵感源于吉老师跳题）

用C语言打造高效题目过滤器：从字符串匹配到模块化设计

在算法竞赛和日常开发中，我们经常需要处理大量文本数据并快速筛选出符合特定条件的内容。想象这样一个场景：你面前有几百道编程题目需要筛选，但只想专注于那些真正具有挑战性的问题，而跳过所有标注为"简单"或"签到"的题目。这正是本文要解决的痛点——我们将用C语言构建一个高效的题目过滤器，不仅能处理固定关键词，还能灵活适应各种过滤需求。

1. 需求分析与核心设计

任何工具开发的第一步都是明确需求。我们的题目过滤器需要实现以下核心功能：

• 实时文本输入处理：能够逐行读取用户输入或文件内容
• 关键词匹配机制：准确识别包含特定词汇的文本行
• 可配置的过滤规则：允许用户自定义需要跳过的关键词
• 结果输出：清晰展示过滤后的内容或统计信息

技术选型对比：

对于我们的需求，简单字符串匹配已经足够，但我们会保留扩展性，以便未来升级到更复杂的匹配方式。

2. 基础实现：字符串匹配核心

让我们从最基础的版本开始——实现一个能够识别并跳过包含"easy"或"qiandao"的题目过滤器。

#include <stdio.h> #include <string.h> #include <stdbool.h> #define MAX_LINE_LENGTH 501 bool should_skip_line(const char* line) { return strstr(line, "easy") != NULL || strstr(line, "qiandao") != NULL; } int main() { char line[MAX_LINE_LENGTH]; printf("请输入题目列表(空行结束):\n"); while (fgets(line, MAX_LINE_LENGTH, stdin)) { // 去除末尾换行符 line[strcspn(line, "\n")] = '\0'; // 空行表示输入结束 if (strlen(line) == 0) break; if (!should_skip_line(line)) { printf("保留: %s\n", line); } else { printf("跳过: %s\n", line); } } return 0; }

这个基础版本已经实现了核心功能：

1. 使用fgets安全读取输入行
2. 通过strstr函数检查关键词
3. 模块化设计should_skip_line函数便于后续扩展

注意：在实际算法竞赛中，通常不需要处理用户交互，而是直接从标准输入读取数据。我们这里的交互式设计是为了便于演示和测试。

3. 进阶功能：支持自定义关键词

固定关键词显然不够灵活，让我们升级程序，允许用户自定义需要过滤的词汇。

#include <stdlib.h> // 动态关键词列表结构 typedef struct { char** keywords; int count; int capacity; } KeywordList; void init_keyword_list(KeywordList* list, int initial_capacity) { list->keywords = malloc(initial_capacity * sizeof(char*)); list->count = 0; list->capacity = initial_capacity; } void add_keyword(KeywordList* list, const char* keyword) { if (list->count >= list->capacity) { list->capacity *= 2; list->keywords = realloc(list->keywords, list->capacity * sizeof(char*)); } list->keywords[list->count] = strdup(keyword); list->count++; } bool should_skip_line_advanced(const char* line, const KeywordList* list) { for (int i = 0; i < list->count; i++) { if (strstr(line, list->keywords[i]) != NULL) { return true; } } return false; } void free_keyword_list(KeywordList* list) { for (int i = 0; i < list->count; i++) { free(list->keywords[i]); } free(list->keywords); }

现在，我们的过滤器可以这样使用：

int main() { KeywordList skip_list; init_keyword_list(&skip_list, 4); // 添加默认关键词 add_keyword(&skip_list, "easy"); add_keyword(&skip_list, "qiandao"); printf("请输入要过滤的关键词(空行结束):\n"); char input[100]; while (fgets(input, sizeof(input), stdin)) { input[strcspn(input, "\n")] = '\0'; if (strlen(input) == 0) break; add_keyword(&skip_list, input); } printf("\n请输入题目列表(空行结束):\n"); char line[MAX_LINE_LENGTH]; while (fgets(line, MAX_LINE_LENGTH, stdin)) { line[strcspn(line, "\n")] = '\0'; if (strlen(line) == 0) break; if (!should_skip_line_advanced(line, &skip_list)) { printf("保留: %s\n", line); } } free_keyword_list(&skip_list); return 0; }

这个版本引入了动态内存管理，使程序能够：

• 运行时动态添加过滤关键词
• 自动扩展关键词列表容量
• 正确释放所有分配的内存

4. 性能优化与错误处理

随着功能增强，我们需要关注程序的健壮性和效率。以下是几个关键优化点：

输入处理优化：

• 使用更安全的输入函数防止缓冲区溢出
• 添加输入长度检查
• 处理可能的读取错误

bool safe_read_line(char* buffer, int size, FILE* stream) { if (fgets(buffer, size, stream) == NULL) { return false; } // 检查是否读取了完整行 if (strchr(buffer, '\n') == NULL) { // 行过长，清空输入缓冲区 int c; while ((c = getchar()) != '\n' && c != EOF); return false; } buffer[strcspn(buffer, "\n")] = '\0'; return true; }

匹配算法优化： 对于大量关键词，简单的线性搜索效率不高。我们可以：

1. 使用更高效的数据结构（如Trie树）
2. 实现多模式匹配算法（如Aho-Corasick）
3. 添加大小写不敏感匹配选项

// 大小写不敏感的字符串查找 bool strstr_case_insensitive(const char* haystack, const char* needle) { while (*haystack) { const char* h = haystack; const char* n = needle; while (*h && *n && tolower(*h) == tolower(*n)) { h++; n++; } if (*n == '\0') return true; haystack++; } return false; }

错误处理增强：

• 检查内存分配结果
• 添加合理的错误消息
• 确保资源正确释放

void* safe_malloc(size_t size) { void* ptr = malloc(size); if (ptr == NULL) { fprintf(stderr, "内存分配失败\n"); exit(EXIT_FAILURE); } return ptr; } void* safe_realloc(void* ptr, size_t size) { void* new_ptr = realloc(ptr, size); if (new_ptr == NULL) { fprintf(stderr, "内存重新分配失败\n"); free(ptr); exit(EXIT_FAILURE); } return new_ptr; }

5. 工程化扩展：模块化与测试

为了让代码更易于维护和扩展，我们应该：

1. 将不同功能分离到独立源文件中
2. 编写单元测试验证核心功能
3. 添加文档注释

推荐的文件结构：

filter_tool/ ├── include/ │ ├── filter.h │ └── keyword_list.h ├── src/ │ ├── filter.c │ ├── keyword_list.c │ └── main.c ├── tests/ │ └── test_filter.c └── Makefile

示例测试用例：

#include "filter.h" #include "keyword_list.h" #include <assert.h> void test_keyword_matching() { KeywordList list; init_keyword_list(&list, 2); add_keyword(&list, "test"); add_keyword(&list, "example"); assert(should_skip_line_advanced("This is a test", &list) == true); assert(should_skip_line_advanced("No keywords here", &list) == false); assert(should_skip_line_advanced("EXAMPLE case", &list) == false); free_keyword_list(&list); } int main() { test_keyword_matching(); printf("所有测试通过!\n"); return 0; }

6. 实际应用场景扩展

这个文本过滤器虽然源于算法竞赛题目筛选，但其应用场景远不止于此：

• 日志分析：过滤掉无关的调试信息
• 代码审查：标记包含特定模式或潜在问题的代码
• 内容审核：识别并过滤不当内容
• 数据处理：清理数据集中的特定条目

性能对比测试： 我们对不同实现进行了性能测试（处理100万行文本）：

结果显示，对于少量关键词，简单字符串匹配仍然是最快选择。但随着关键词数量增加，专门的多模式匹配算法优势明显。

7. 进一步优化方向

如果你想让这个工具更加强大，可以考虑：

1. 支持正则表达式：使用POSIX正则表达式库或PCRE
2. 添加文件输入/输出：处理大型文本文件
3. 实现并行处理：利用多线程加速过滤过程
4. 构建交互式界面：使用ncurses创建终端UI
5. 添加统计功能：记录过滤结果的数量和类型

// 简单的正则表达式匹配示例 #include <regex.h> bool regex_match(const char* pattern, const char* text) { regex_t regex; int ret; if (regcomp(&regex, pattern, REG_EXTENDED) != 0) { return false; } ret = regexec(&regex, text, 0, NULL, 0); regfree(&regex); return ret == 0; }

在实际项目中，我发现最影响使用体验的往往不是核心功能，而是输入/输出处理和错误恢复。一个健壮的工具应该能够优雅地处理各种边界情况，并提供清晰的反馈。