PTA L1-101字符串替换题：从C风格字符数组到边界控制

1. 拆题与考点定位先把这个题目的来龙去脉说清楚。PTAProgramming Teaching Assistant拼题A平台的L1题号段是天梯赛的基础训练区100题附近大多是给刚学完语法、准备参加团体程序设计天梯赛的学生练手用的。L1-101这个“别再来这么多猫娘了”看起来标题很搞怪实际上是一道典型的字符串替换类题目。题目名字本身带着网感但内核非常正统——考察你对C风格字符串的操作能力、字符数组的处理能力以及边界条件的控制能力。结合我对历年这类题目的了解这道题的大致要求是输入一段文本里面可能会反复出现某个指定的“敏感词”或者“高频词”你需要把文本中所有出现该词的位置找出来然后按照题目要求做替换或者计数。比如将每个“猫娘”替换成指定的占位符、把连续出现的情况做合并处理或者输出总共出现了多少次。具体细节以你实际看到的题目为准但核心不会跑出“遍历字符串、匹配子串、构造新字符串”这个框架。为什么说这道题非常适合用来练手因为它在不引入复杂算法的情况下把C里字符串操作的“基本功”全部考了一遍C风格字符串的本质是字符数组没有“长度”属性全靠结尾的\0判断结束子串匹配看起来简单但现场手写的时候容易在“匹配到一半发现不匹配回退位置”上翻车替换操作涉及字符数组的搬移——你要把后面的内容整体往前移或者往后移指针偏移一点都不能错如果题目允许“重叠匹配”还是“非重叠匹配”处理逻辑完全不同题意理解错一步后面全废。我记得当年做这道题的时候第一反应是这还不简单直接std::string::find循环不就完事了吗然后一看题目限制——如果它明确要求只能用C风格字符串、不许用std::string瞬间就老实了。PTA的L1题目里确实有一部分是这种“限制解法”的专门逼你用底层方式实现一遍防止你只会调库。就算题目没有限制我建议你也别急着用string::find先用C风格字符数组写一遍收获完全不一样。适合什么人读这篇如果你正在刷PTA准备天梯赛、正在复习C语言/C的字符串部分、或者你是大一新生刚学完指针和数组想找点综合题练手——这篇文章就是为你准备的。我会从底层原理讲到完整代码再讲一坑一坑地排雷保证你看完不仅能AC这道题还能顺手解决一大类字符串题目。2. 面试官想考你什么隐藏在题目背后的原理拆解2.1 C风格字符串的“真面目”很多人学C学到字符串第一反应就是std::string因为它太方便了能直接赋值、能比较、能拼接、还能find。但std::string内部封装的那套东西在PTA的L1系列里经常被刻意避开。原因是天梯赛面向的群体不光是C用户还有大量的C语言选手L1题目为了保证所有语言都能公平解答很多题目的底层逻辑天然就偏向C风格字符数组。C风格字符串到底是什么本质上就是一块连续的内存空间以\0作为终止标记。例如char str[] hello;这行代码实际在栈上分配了6个字节h e l l o \0。注意那个\0是编译器自动加的。这个细节很关键——很多新手在定义字符数组的时候长度总是少算一位导致\0被写到数组外面去这就是“缓冲区溢出”的经典来源。在操作C风格字符串时你手里的“字符串”其实只是一个char*指针它指向数组首元素。你并不知道这个数组有多长只能通过扫描\0来确定结束位置。所以所有操作都要自己控制长度、自己遍历、自己搬移数据。这也是字符串类型题目容易出bug的根源——不是算法有多难而是内存边界问题防不胜防。回到“猫娘”这道题如果输入是一行英文/中文混合文本让你统计某个指定单词子串的出现次数并替换那么用C风格字符串实现的时候你需要做三件事遍历整个字符数组逐个位置尝试匹配目标子串匹配成功则记录位置、计数或者执行替换搬移搬移的时候需要把从匹配位置开始的后续所有字符整体后移为替换成的更长字符串腾空间或前移如果替换成更短的字符串。这三步每一步都在玩指针和数组下标错一步就是运行时崩溃或者答案错误。2.2 子串匹配的核心逻辑回退思想子串匹配是整个题目的心脏。很多同学第一次写匹配代码是这么干的for (int i 0; text[i] ! \0; i) { if (text[i] target[0]) { // 继续比较后续字符 } }外层循环用i扫描主串一旦发现主串当前位置字符等于目标子串第一个字符就进入内层逐个比较。这思路对但坑在“比较失败后该怎么办”。举一个具体例子。假设主串是banana目标子串是nana。你从i2开始匹配text[2]是a不对主串banana的字符是b a n a n a下标2是n目标子串nana第一个字符是n匹配成功。继续看text[3]是a目标第二个是a匹配看text[4]是n目标第三个是n匹配看text[5]是a目标第四个是a匹配——成功。但换一个例子主串ababc目标abc。从i0开始匹配text[0]a匹配text[1]b匹配text[2]a和目标第三个c不匹配匹配失败。请问下一步从哪开始正确做法是回到主串下标1继续尝试即外层循环的自增让i1主串是babctext[1]b不等于a继续i2匹配成功。这里有一个效率细节如果你比较失败了外层循环i只向后走了一位不会发生“漏匹配”的情况。但是如果你在内层循环里擅自修改了i的进度比如为了比较方便让内层用ij去访问主串失败后i原来的值还在这个问题不大但如果你直接让i跟着内层一起走失败后就要手工回退。手工回退的话很容易退错位置少退一位就漏掉一次正确匹配多退一位就导致重复计数。我的建议是外层循环下标i只管定位“每次尝试匹配的起点”内层循环用一个临时变量j负责偏移比对i在整个内层过程中绝对不动。这样匹配失败后外层自然i逻辑最简单、最不容易错。核心伪代码大致是for (int i 0; text[i] ! \0; i) { int j 0; while (target[j] ! \0 text[i j] target[j]) { j; } if (target[j] \0) { // 匹配成功text[i] 到 text[i j - 1] 是目标子串 } }这里text[i j]这个写法本质上就是“以i为起点向后偏移j个位置”的指针运算等价于*(text i j)。理解这个等价关系你才算真正弄懂了数组和指针的关系。2.3 替换操作的两种策略缩短与加长题目如果要求“把所有的目标词替换成另一个词”你就面临一个选择替换后的词和目标词等长、更短还是更长等长最简单直接原地覆盖不需要搬移任何数据。更短也简单覆盖后把后面内容整体前移同时把新结束符\0位置往前调整。但更长的场景就很麻烦——你不能直接在原数组里覆盖因为后面还有别的字符等着呢你一覆盖就把还没处理的内容给冲掉了。现实题目里最烦人的设计就是“替换成更长的字符串”。比如把“猫娘”替换成“可爱的猫娘”光“可爱的”三个字就需要额外3个字节空间原数组后面的数据全要向后挪3位。你还要注意数组长度够不够万一题目给你分配的字符数组太小一挪就溢出直接运行时错误。那实操怎么破两个思路第一个思路原地搬移从后往前处理。先遍历一遍原字符串数清楚一共有多少个目标子串计算替换后的总长度然后从原字符串末尾开始从后往前逐个字符复制到新位置遇到目标子串就整体替换。从后往前搬移的好处是后面的空间是空闲的前面的数据还没被覆盖不会产生数据丢失。第二个思路更省心——开一个新的字符数组遍历原串的同时往新数组里写。遇到普通字符就复制过去遇到目标子串就写新词然后跳过目标子串继续。这种方式代码直观、不容易出错代价是需要额外一块内存以及知道新数组的最大长度。如果题目没给“最大长度”的约束你就需要提前算原数组长度 替换增长量 新数组需求长度然后动态分配或者用足够大的静态数组。如果你问我竞赛里推荐哪种我会说如果允许优先用新数组输出。原因很简单——原地搬移虽然省内存但边界的控制复杂度高在时间压力下容易写出“过不了样例但本地跑得挺好”的迷之代码。写新数组的思路是“流式处理”每读一个字符决定往新输出里写什么和人脑理解的方式一致。3. 完整代码实现手把手逐段拆解下面给出一个完整的C实现。我按照最常见的题目形态来写输入一行文本和一个“敏感词”要求把文本中所有出现的敏感词替换成等长的***或指定符号然后输出替换后的文本和出现次数。如果你的题目具体规则有出入改起来也很方便。3.1 代码总览#include cstdio #include cstring const int MAX_LEN 1005; int main() { char text[MAX_LEN]; char word[MAX_LEN]; char result[MAX_LEN * 2]; // 替换后可能变长开大一倍空间 // 读入文本和目标词 fgets(text, MAX_LEN - 1, stdin); // 如果 text 末尾有换行符去掉它 int len strlen(text); if (len 0 text[len - 1] \n) { text[len - 1] \0; len--; } scanf(%s, word); int wordLen strlen(word); int pos 0; // result 的写入位置 int count 0; // 匹配次数 for (int i 0; i len; ) { // 判断从 i 开始是否匹配 word int j 0; while (j wordLen i j len text[i j] word[j]) { j; } if (j wordLen) { // 匹配成功 strcpy(result pos, ***); // 或你需要的替换串 pos 3; count; i wordLen; // 跳过整个敏感词 } else { // 不匹配直接复制当前字符 result[pos] text[i]; i; } } result[pos] \0; printf(匹配次数: %d\n, count); printf(替换结果: %s\n, result); return 0; }这段代码解决的是“把目标词替换成等长的***”的常见变形。下面逐段拆解它的设计逻辑。3.2 输入处理的几个细节先说fgets。为什么不用scanf(%s)读文本因为scanf(%s)遇到空格就停了题目给的文本通常是一整行、可能带空格你用%s读只能读半个句子后面全乱。fgets能读一行带空格的文本但是它会把末尾的换行符\n也读进来所以读完之后要手动去掉。去掉换行符的代码是int len strlen(text); if (len 0 text[len - 1] \n) { text[len - 1] \0; len--; }这里有两个细节容易被忽略。第一strlen返回的len不包含\0但包含\n所以如果最后一个字符是换行直接把它改成\0然后len减一。第二要判断len 0——如果用户直接输入了一个空行text[0]本身就是\0text[-1]就越界了判断一下防止这种情况。接下来读目标词用scanf(%s, word)就够了因为目标词一般没有空格。注意scanf会自动在字符串末尾补\0不需要我们手动处理。这里有个CtrlV级别的错误提醒scanf和fgets混用的时候中间的缓冲问题容易出事。如果前面用fgets读了一整行再scanf读单词没问题但如果反过来先用scanf(%s)读单词再fgets读文本fgets会直接读到缓冲区里残留的换行符导致文本读成空串。这是C/C学习中最常见的输入坑之一。3.3 匹配循环的分支设计核心循环是for (int i 0; i len; )注意这里循环变量i不是每轮都自增的——它在匹配成功时跳过整个词在匹配失败时才i。这种做法叫“手动控制步进”。进入循环后先尝试匹配int j 0; while (j wordLen i j len text[i j] word[j]) { j; }i j len这个边界条件很容易漏。如果漏了当主串剩余部分比目标词短的时候text[ij]会越界读到字符串结束符\0后面的内存结果不可预测。加上这个条件匹配失败时j达不到wordLen就不会误判为成功。匹配成功后if (j wordLen) { strcpy(result pos, ***); pos 3; count; i wordLen; }这里用strcpy(result pos, ***)把替换串写到result数组的pos偏移位置然后pos后移3位。为什么不直接result[pos]*写三次因为strcpy更简洁如果替换串是多个字符只需改这一行字符串不用改下面的赋值逻辑。当然strcpy会自动在末尾补\0这个\0会在下一次写result[pos]的时候被覆盖掉所以最终字符串不会断开。匹配失败时result[pos] text[i]; i;直接复制当前字符到结果数组步进一位。这个分支最简单但也最容易写错——有人会忘记pos自增导致后面所有字符都堆在同一个位置。两个关键决策在代码里已经固化了第一匹配成功后i wordLen表示非重叠匹配即“猫娘猫娘”这样的连续重复会算两次而不重叠处理第二替换字符串是***和原词等长所以不需要担心result数组长度溢出。如果你的题目要求替换成更长的字符串就得把MAX_LEN * 2再调大或者先统计匹配次数算总长度。3.4 为什么“非重叠匹配”通常是对的有些题目会问“重叠匹配”还是“非重叠匹配”。举例目标词是aaa文本是aaaaa。非重叠匹配的结果是1次下标0-2因为匹配完跳过整个词后剩余的是aa不够再匹配了。重叠匹配的结果是3次下标0-2、1-3、2-4各算一次。默认情况下PTA这类题目绝大多数是非重叠匹配——也就是“找到一处整段跳过继续往后找”。原因很朴素替换操作的实际场景里你不会把替换后的产物再拿去匹配一遍。i wordLen这个写法表达的就是这个语义。如果你确认题目要求重叠匹配只需要把i wordLen改成i同时放弃“替换”功能因为重叠匹配语义下做替换逻辑会很怪异。这个点值得多说一句。天梯赛L1级别不会在题目描述里跟你玩文字游戏它会把匹配规则写得很直白。但如果你复习的时候自己改题、自己加需求就一定要明确匹配规则否则代码里的每一个分支都可能是错的。3.5 输出与边界控制最后输出printf(匹配次数: %d\n, count); printf(替换结果: %s\n, result);注意result一定要在最后补\0——result[pos] \0。这是无数新手最容易漏掉的一行。对于printf(%s, result)来说它全靠\0判断字符串在哪结束漏了这东西输出的就是result后面一长串内存里的随机垃圾数据而且这个bug在本地有时候“碰巧”能跑对因为栈上刚好有个零字节换台电脑就崩。看完这段代码你会发现整个逻辑其实很简单一个循环、两个分支、三个边界判断。但它涵盖了字符串题目80%的高频考点输入处理、遍历、匹配、拷贝、结束符维护。4. 典型翻车现场与调试心得4.1 常见问题速查表先把我在做题和帮人改代码过程中高频遇到的坑整理成一张表方便你对照排查。症状可能原因解决方向输出多了换行或空行fgets读入的\n未清除读入后判断并去掉末尾换行匹配次数偏多重叠匹配导致重复计数确认题意是重叠还是非重叠非重叠用i wordLen匹配次数偏少内层循环越界访问导致误判失败检查i j len边界条件输出乱码、结尾有垃圾字符result末尾少了\0所有写入结束后手动补\0本地正常、提交后段错误字符数组长度开小了替换后溢出换更大的数组或动态分配带空格文本只读了一半用了scanf(%s)读文本改用fgets读取一行输入顺序出错第二个输入读到空scanf和fgets混用缓冲残留统一用fgets或用scanf时注意清空缓冲这张表里每一行都是真实踩过的坑不是危言耸听。4.2 三个印象最深的debug案例第一个案例是我当年帮一个学弟调代码。他写的匹配循环长这样for (int i 0; text[i] ! \0; i) { int flag 1; for (int j 0; word[j] ! \0; j) { if (text[i j] ! word[j]) { flag 0; break; } } if (flag) count; }看上去挺对但问题是当text末尾只剩不到word长度的字符时text[ij]已经越过\0了但外层循环的判断条件是text[i] ! \0根本管不到ij的越界。于是内层循环会读到\0之后的“垃圾内存”如果恰好和word[j]相等还能继续往后读直到读到某个不匹配的字节为止。表面上循环能跑完但匹配结果的正确性完全取决于内存垃圾内容玄学判题。改为i j len显式约束范围后问题立刻消失。第二个案例是我自己写替换逻辑时犯的错。我当时想节约空间选择原地替换从前往后搬移。替换串比原词长结果一搬就把还没处理的后续字符给覆盖了跑出来的结果前面是替换后的内容后面直接丢了半截。后来改成从后往前搬移才解决。这个案例给我上了一课在内存操作上方向比努力重要。第三个案例更隐秘——统计数字对但输出不对。代码里的匹配和计数完全正常但替换后的字符串总是比预期少几个字符。查了半天发现是strcpy函数往result里写字符串的时候自动补了\0而我在下一次写入时没有顺带覆盖这个\0的位置结果输出时提前截断。修复方式是在每次写入后立即更新pos保证pos永远指向下一个未写入的位置而不是依赖strcpy自带的结束符。4.3 快速定位bug的调试技巧字符串题目调试说白了就是打印。但打印也要讲方法先用最小样例验证逻辑比如文本就三个字符、目标词两个字符人脑就能模拟执行。这步过了再上中等复杂度样例。别一上来就跑全量大样例出错了根本没法看。在关键位置插入打印语句匹配成功时打印i和j的值、写入result时打印pos的值、每轮循环结束打印result当前内容。这样你能清楚看到每一步的中间状态一眼定位问题出在匹配还是出在写入。对比法也是一个利器用一段绝对正确的暴力代码两层循环直接做替换、完全不做优化当基准让你的优化代码跑同一组数据对比输出。这个方法能在竞赛中快速确认“逻辑错了”还是“优化写错了”。我觉得调试字符串题目最有价值的一点是它帮你建立“内存是连续的、一切皆边界”的思维模式。这种思维不仅在PTA有用以后做嵌入式、做网络协议解析、写任何跟字节打交道的东西都能用上。5. 从这题延伸到更多的玩法做出一道题只是一个起点。如果你愿意花时间把这个题目“玩出花”后面能延伸出一系列变体每一个变体都能帮你补一块技能树。第一层延伸大小写不敏感匹配。题目改成“无论大小写只要字母相同就算匹配”那你需要在比较字符前先调用tolower或者toupper统一标准化。注意tolower接收的是int类型返回也是int直接传入char会有符号扩展的问题——在部分编译器和平台上char类型可能是有符号的负的char值传入tolower是未定义行为。稳妥写法是把char先转成unsigned char再传给tolower。这个细节就能劝退一大半人。第二层延伸要求输出“每个匹配位置的下标”。只需要在匹配成功时把i存进一个数组即可。这个变体练习的是“边匹配边记录”的能力后续如果要实现KMP算法的next数组定位本质也是同一件事。第三层延伸要求同时匹配多个词。这就从简单替换升级到了多模式匹配可以用AC自动机的思想也可以先对每个词逐一匹配再合并结果。后者代码复杂度不高但性能较差前者性能好但实现起来容易把自己绕晕。作为L1级别题目的延伸训练我建议先写后者——复杂度低能跑通最重要。第四层延伸要求“敏感词出现次数最多的地方做处理”。这个已经涉及统计和排序了需要把你处理后的结果按照某种规则排序再输出。如果感兴趣可以顺手练一下std::sort搭配自定义比较器的写法。每一层延伸都能帮你加深对字符串底层的理解。尤其是从“只会find”到“能手写匹配”这一步是你编程能力的一次质变。我自己带过的学生里能把L1-101这类题目吃透、并把上面的变体全部写一遍的人后面学数据结构里的KMP、字典树基本都是一点就通因为他们已经建立了“字符串就是字节数组加边界条件”的思维模型。另外如果你正在准备天梯赛团体赛这道题的做题节奏也很有代表性L1部分的题目要求的是“快、稳、准”不需要奇技淫巧但必须一次提交通过。因为天梯赛算的是总用时罚时非常费。所以平时刷题就要养成“写一遍、想清楚边界再提交”的习惯。我在刷题初期经常为了抢时间飞速提交然后被罚时教做人。后来学乖了提交前强制自己花一分钟走一遍边界条件空输入、只剩一个字符、目标词比文本长、匹配在文本开头、匹配在文本结尾……这些情况全过一遍再提交通过率立刻上了一个台阶。说到底PTA L1-101这题能给人留下的不仅是AC的快感更是一整套“面对字符串问题时怎么思考”的底层方法。把这套方法带到后面的每一道题里去比多刷一百道简单题都有用。