别再暴力遍历了！用C语言strchr函数5分钟搞定PTA L1-011 A-B字符串过滤

用C语言strchr函数高效解决PTA字符串过滤问题在编程竞赛和在线评测系统(如PTA)中字符串处理是最基础也最常遇到的题型之一。许多初学者面对A-B这类字符串过滤问题时第一反应往往是使用暴力双循环遍历——这种解法虽然直观但效率低下且代码冗长。实际上C语言标准库中已经提供了strchr这样强大的字符串查找函数只需5分钟理解其用法就能写出比暴力解法更高效、更优雅的代码。1. 理解PTA L1-011 A-B问题本质PTA平台上的L1-011题目要求我们实现一个字符串过滤功能从字符串A中删除所有出现在字符串B中的字符然后输出剩余字符组成的新字符串。例如输入 I love GPLT! Its a fun game! aeiou 输出 I lv GPLT! Its fn gm传统暴力解法通常会这样实现for (int i 0; i strlen(A); i) { int found 0; for (int j 0; j strlen(B); j) { if (A[i] B[j]) { found 1; break; } } if (!found) { printf(%c, A[i]); } }这种解法的时间复杂度是O(n²)当字符串长度达到题目上限10⁴时性能会明显下降。而使用strchr函数可以将时间复杂度优化到O(n)。2. strchr函数的工作原理与优势strchr是C语言标准库string.h中提供的字符串查找函数其原型为char *strchr(const char *str, int ch);该函数会在字符串str中查找字符ch第一次出现的位置如果找到则返回指向该位置的指针否则返回NULL。它的内部实现通常经过高度优化比手写的遍历查找效率更高。使用strchr优化A-B问题的核心思路遍历字符串A的每个字符使用strchr在字符串B中查找当前字符只有当strchr返回NULL时才输出该字符优化后的代码示例如下#include stdio.h #include string.h int main() { char A[10001], B[10001]; fgets(A, sizeof(A), stdin); fgets(B, sizeof(B), stdin); size_t len strlen(A); for (size_t i 0; i len; i) { if (!strchr(B, A[i])) { putchar(A[i]); } } return 0; }3. 关键实现细节与注意事项3.1 输入处理的最佳实践在PTA等OJ平台中正确处理输入是解题的第一步。需要注意使用fgets而非gets因为后者已被弃用且存在缓冲区溢出风险处理输入字符串末尾的换行符考虑字符串可能包含空格的情况改进后的输入处理代码fgets(A, sizeof(A), stdin); A[strcspn(A, \n)] \0; // 移除换行符 fgets(B, sizeof(B), stdin); B[strcspn(B, \n)] \0;3.2 性能优化技巧虽然strchr已经比暴力解法高效但还可以进一步优化预先计算字符串长度避免在循环中重复调用strlen使用指针运算减少数组索引操作考虑字符集特性如果知道B中字符范围有限可以用查表法优化后的遍历代码const char *p A; while (*p) { if (!strchr(B, *p)) { putchar(*p); } p; }3.3 边界条件处理在实际编程竞赛中必须考虑各种边界条件空字符串输入字符串全匹配的情况包含特殊ASCII字符的情况最大长度测试用例4. 扩展应用与思维训练掌握strchr的用法不仅能解决A-B问题还能应用于许多其他场景字符串分割查找分隔符位置字符分类统计快速判断字符是否属于某集合简单模式匹配实现基础的通配符查找在编程竞赛中培养标准库优先的思维非常重要。C语言标准库中还有许多类似strchr的高效函数strstr查找子字符串strpbrk查找一组字符中的任意一个strspn/strcspn计算匹配/不匹配的初始段长度理解这些函数的内在联系能够帮助我们在面对字符串处理问题时快速选择最合适的工具。