字符串匹配与输入终止条件：吃火锅竞赛题全解析与常见坑

自打开始刷程序设计竞赛的基础题我就发现一个规律越是分值看着不起眼的题越爱在细节里埋坑。“L1-070 吃火锅 - 15 分”就是这么一道题。你说它难吧核心逻辑就是个字符串匹配你说它简单吧我在练习时见过不少人在“输入终止条件”和“输出顺序”上翻车白白丢分。这篇博文就把这道题从题目拆解到代码落地再到底层原理和常见坑完整捋一遍希望对正在刷天梯赛基础题的朋友有帮助。1. 题目分析与解题思路拆解1.1 题目到底在问什么先还原一下题目的真实场景。你是一个负责统计的人面前是一堆聊天记录每行一条消息。你的任务是检查这些消息里有没有提到“火锅”或者某个指定的菜品关键词。如果提到了就算一条有效记录最后要数一数总共有多少条有效记录并且把第一条有效记录的行号输出出来。听起来很直接对吧但题目里有一个很关键的前提输入是一行一行给出的直到遇到一个单独的英文句号“.”为止。也就是说这个“.”不是消息内容而是终止信号读到它就必须停止处理而且在统计结果里不能算进去。还有一个隐藏的细节题目要求的是“输出有效记录的总条数”和“第一条有效记录是在第几行”。注意这里的“第几行”是从输入开始逐行数的包括那些没有提到关键词的行也包括最后那个终止符“.”所在的行吗答案是不把它算进去因为读到“.”就结束循环了不会继续往下数行号了。这个点在实现时要格外小心。1.2 核心考点拆解这道题是典型的基础字符串处理题考察点可以拆成四个维度字符串子串匹配你需要判断一行文本里是否包含目标关键词。输入流的终止条件处理什么时候停止读入用什么标志位。计数器与标志位的配合既要统计总数又要记录第一个命中项的位置。边界输入的处理比如空行、只含关键词的行、关键词出现在句子中间的行、完全没有关键词的输入。很多人看到“吃火锅”这个标题就以为是模拟题其实考察的核心是“在一个字符串序列里做条件筛选并统计”这在很多真实业务场景里都会用到比如日志筛选、关键词报警、热词统计等。所以别觉得这题只是竞赛玩具它的思路是可以直接迁移的。1.3 为什么选择这种考察方式我个人的理解是这类基础题的目的不是考你算法多精妙而是考你有没有养成严谨的输入处理习惯。竞赛里有一类很典型的丢分方式你算法写对了但循环多读了一行或者把终止符当成普通数据处理了结果整个统计全部错位。这种错误恰恰是生产环境里最容易出问题的——接口返回了空值你没判、日志文件末尾多了个EOF标记你没处理、用户输入了终止指令你还在继续跑。所以这道题的隐藏考点其实是“什么时候该停”而不仅仅是“怎么匹配”。理解了这一点你再看它就只有一层窗户纸了。2. 字符串匹配方案选型与原理剖析2.1 几种字符串匹配方案对比判断一行字符串里是否包含另一个字符串在主流编程语言里都有现成方法。以Python为例最常见的是用in关键字以C为例常用string::find。我们来对比一下几种方案的细节差异。方案实现方式时间复杂度适用场景坑点Pythonin底层调用快速搜索算法通常是Boyer-Moore或类似优化平均O(n)最坏O(n*m)大多数日常判断无需手动处理但别在循环里重复做重活Cstring::find通常实现为朴素匹配或针对短串优化的混合算法O(n*m)最坏实际效率尚可小众关键词匹配返回值是string::npos别写成 -1的硬比较正则表达式编译模式后匹配匹配速度取决于模式复杂度需要模式匹配如“火锅\d”过度设计小题大做手动实现KMP构建部分匹配表线性扫描O(nm)关键词很长且需要大量复用代码量大题没必要用对于“吃火锅”这道题关键词是固定的、短的输入量也不算大用现成方案就够了。我见过有人为了追求极致效率在这道题上手写KMP结果代码比题面还长属实没必要。选型的核心原则是在满足题目约束的前提下用最简单、最不容易出错的方案。2.2 为什么字符串匹配不能忽略大小写和空白这个点很多人会忽略。题目里的聊天记录可能是用户随手发的可能带空格、可能是英文单词、可能有大小写差异。如果关键词是“hotpot”那“Hotpot”算不算命中从自然语言处理的角度应该算但竞赛题如果不专门说明“忽略大小写”那就严格按字面匹配来。实操中我的建议是先看一眼题目有没有提“不区分大小写”没提就默认区分。至于空白字符比如一行是“我想吃 火锅”中间有空格这种情况下包含关系依然成立因为空格不影响“火锅”作为一个连续子串存在。但如果关键词恰好被拆成“火 锅”那就匹配不到了这是符合题意的。2.3 匹配算法的效率在这里真不重要再强调一次这道题的分值只有15分数据规模一般不会很大。按天梯赛L1级别的惯例输入行数通常在小几十行以内每行长度也就几十到一百字符。这个规模下哪怕是O(n*m)的朴素匹配也就是微秒级的事根本不需要什么高端优化。与其纠结匹配算法不如把精力花在输入读取出错的边界条件上。后面我会详细讲这道题真正的分水岭在输入循环的终止条件以及你对“行号”的定义方式上。3. 完整实现与关键步骤复盘3.1 Python参考实现我先给一版可用的Python实现再逐步拆解。import sys def main(): keyword 火锅 # 这里假设题目要求匹配的关键词是“火锅” total 0 first_line 0 line_no 0 for line in sys.stdin: line line.rstrip(\n) line_no 1 if line .: break if keyword in line: total 1 if first_line 0: first_line line_no if total 0: print(0) else: print(total) print(first_line) if __name__ __main__: main()几个细节我解释一下rstrip(\n)是为了去掉每行末尾的换行符避免判断line .时因为尾部有换行符而匹配失败。有些人用strip()也可以但注意strip()会去掉行首行尾的所有空白字符如果聊天记录里有一行内容前后有空格strip()会改变内容。用rstrip(\n)更精确。line_no 1放在判断终止符之前是因为终止符所在的行也需要占用一个行号。不过因为我们遇到终止符就break了所以这个行号不会被使用实际上没有影响。first_line 0用来标记“还没记录过第一个命中行”因为行号从1开始所以0可以作为未初始化的标志。这个技巧在竞赛代码里很常见能省一个布尔变量。3.2 C参考实现如果你用C刷题实现会稍微注意一下getline的用法。#include iostream #include string int main() { std::string keyword \u706b\u9505; // 火锅 std::string line; int total 0; int first_line 0; int line_no 0; while (std::getline(std::cin, line)) { line_no; if (line .) { break; } if (line.find(keyword) ! std::string::npos) { total; if (first_line 0) { first_line line_no; } } } if (total 0) { std::cout 0 std::endl; } else { std::cout total std::endl; std::cout first_line std::endl; } return 0; }C版本的核心判断是line.find(keyword) ! std::string::npos。npos是string类里一个静态常量表示“没有找到”。我看到有些初学者会写成line.find(keyword) 0这在逻辑上是错的因为find返回的是size_type类型无符号永远大于等于0。正确的判断就是和npos比较。3.3 手动模拟一遍完整输入输出光贴代码不够我手动跑一组数据直观展示程序的行为。假设输入如下我想吃火锅 今天天气不错 海底捞的火锅真好吃 。逐行分析行号内容是否包含“火锅”累计totalfirst_line1我想吃火锅是112今天天气不错否113海底捞的火锅真好吃是214.终止break--最后输出2 1再跑一组没有命中任何关键词的输入你好 再见 。输出就只有一个0。注意不是输出两行而是只输出一行0。这个输出规则也是题目明确要求的别多输出。4. 常见错误与调试记实录4.1 错误一终止符判断失败这是这道题出现频率最高的错误。很多人读入一行后直接用line .判断但读入的line尾部带着换行符导致字符串是.\n和.不相等于是终止条件永远不触发程序把后面的行全读完才停统计结果错得离谱。这类问题用Python的input()函数时不会出现因为input()会自动去掉尾部换行但用sys.stdin或C的getline时就要特别注意。我的习惯是统一用rstrip(\n)或判断前.strip()除非题目明确说行内可能有需要保留的空格。4.2 错误二输出格式不符合要求题目要求的是“先输出总数再输出第一条命中行的行号”并且是在总数不为0的情况下。有些人习惯把两个结果都输出即使总数是0也输出一个无效的行号。这属于没有仔细读题。如果总数是0只输出一个0即可多输出会被判格式错误。顺便说一句竞赛OJ的判题对空白字符很敏感。多一个空格、多一个空行都可能判Presentation Error也就是格式错误。输出前最后检查一遍print的参数和换行。4.3 错误三行号计数范围搞错有人会把“行号”定义成“关键词命中的第几条”也就是命中第1条、第2条……然后输出命中的序号。这和题目要求的“输入中的行号”完全不是一回事。题目要的是“在全部输入中命中关键词的第1行排在第几行”所以计数的是输入的行序号不是命中次数。这个错误在样例数据不大时很难发现因为很多样例恰好第一行就命中了两个含义的结果都是1。建议自己构造一组数据测一下比如第一行不命中、第二行命中正确答案的first_line应该是2如果程序输出1就说明你统计错了。4.4 我的排错流程心得遇到这类题目报错我一般按顺序排查先拿题目样例跑一遍这是最基本的。再自己构造几个极端的边界样例比如空输入、第一行就是终止符、全部命中、全部不命中、关键词出现在行首、关键词出现在行尾。检查输入终止逻辑打印每个读入行和行号确认循环何时退出。检查输出逻辑特别注意有无多余空格、空行、换行。这套流程看起来简单但能解决90%以上的基础题问题。很多人喜欢盯着算法想半天其实错的往往是输入输出这种“低级”环节。5. 从竞赛题到工程实践的思维迁移5.1 关键词匹配机制的设计经验这道题虽然只是一个“找关键词并计数”的小任务但它背后对应的工程场景非常多。比如爬虫系统里要统计某个网页是否包含指定敏感词日志系统里要筛选含有特定错误码的行监控系统里要检测几个告警关键词在短期内的出现次数。在这些场景里你会发现“终止条件”往往会变成“超时时间”或“数据量上限”。比如说你要统计一个持续流式输入的日志里过去5分钟内出现了多少次“ERROR”。这时候不能用无限循环得设定窗口这和题目里“读到点号就停”的逻辑是同构的。5.2 匹配方案的升级路径如果将来要处理的数据量变大、关键词变多你可以按这样升级方案单个短关键词、数据量小直接用内置匹配。单关键词、数据量大用KMP或Boyer-Moore甚至用SIMD指令加速。多个关键词、数据量中等用Trie树或多模式AC自动机一次扫描完成多个关键词的匹配。多个关键词、无固定集合用正则表达式或外包给全文检索引擎。我把这些路线列在下面方便参考数据规模关键词数量推荐方案理由小百行级1内置in/find代码简单可读性强大百万行级1KMP / BM线性复杂度耗时可控大多固定集合AC自动机一次扫描匹配所有关键词中大多动态变化正则表达式或索引灵活可维护性好在实际工程里我一般先做性能预估如果预估在可控范围内就直接用最简单的方案只有撑不住了才上复杂算法。这道题考的就是这个判断力你知道什么时候不用KMP比知道怎么写KMP更重要。5.3 个人调试小技巧最后分享一个我刷基础题时常用的调试技巧在代码里加一个调试开关输出每次读入的行和当前的行号。debug True for line in sys.stdin: line line.rstrip(\n) line_no 1 if debug: print(fDEBUG: line_no{line_no}, content{repr(line)}, filesys.stderr) if line .: break ...把调试信息输出到stderr这样不会污染OJ要求的stdout输出。本地测试时能看到完整流程提交时把debug改成False或直接删掉即可。这个习惯帮我省了大量猜错的时间。回头再看这道“吃火锅”题它真正的价值不在于让你学会in或find而在于让你体会“输入边界”的重要性。很多现实世界的数据处理任务最后发现的bug都不是核心逻辑而是“什么时候该停止”没想清楚。把这个习惯养好你后面刷L2、L3的题会顺很多写工程代码也会少踩很多坑。