P1308 统计单词数字符串这是我在某在线判题系统上刷到的第一道让我印象深刻的字符串题。题面很短给一个目标单词再给一段由英文单词和空格组成的文章统计这个单词在文章中出现了多少次并且输出第一次出现的位置。听起来像是一个find或者indexOf就能解决的活但我第一版代码连交了三次都没通过。后来我才意识到这道题考的根本不是「查找子串」而是「精确匹配单词」——你要找的是独立的单词不是藏在其他单词里的字母组合。这篇文章我会把题目背后真正想考的东西拆开讲再给出 C 和 Python 的完整实现最后把我自己踩过的几个坑完整复盘一遍。适合刚开始学字符串处理的同学也适合想在日志分析、文本检索这类场景里做关键词统计的开发者。1. 题目到底在考什么这不是一次简单的字符串查找1.1 输入输出约定和经典样例这道题的输入通常分成两行。第一行是目标单词第二行是一段文章。以我在某在线判题系统上看到的版本为例输出要求是如果单词在文章中出现过输出出现次数和第一次出现的位置中间用空格隔开如果一次都没出现直接输出 -1。样例大概是这样的输入 To To be or not to be 输出 2 1文章里有两个 to忽略大小写第一次出现在文章的第一个单词位置所以答案是2 1。这个样例本身没有任何难度难的是题目随后的边界条件比较时忽略大小写、单词两边必须是空格或边界、位置从 1 开始计数。1.2 三个容易被忽略的隐藏条件很多人在样例过了之后就急着交然后收到一个大大的错误提示。原因通常是下面这三个隐藏条件没有处理好。第一大小写不敏感。目标单词是 To文章里的 to 也算匹配。这意味着不能直接拿原始字符串做比较必须先把两边统一成小写或者大写。这一步本身不难但会引出一个更隐蔽的问题转小写之后位置索引会不会变不会因为转换不改变字符串长度所以找到的位置在原串和新串里是同一个位置。这个推理看着简单实际很多人写代码时会在这里绕晕。第二单词边界。这是整道题的核心考点。目标单词是 to文章里出现 tomorrow 时里面的 to 不能算数。也就是说匹配到的子串前后必须是空格或者位于文章开头/结尾。用编程语言自带的find或indexOf直接找找到的只是子串位置不是单词位置。很多人第一次 WA 就是挂在 tomorrow 这种词上。第三位置从 1 开始计数。如果文章以目标单词开头位置是 1不是 0。这个约定看起来不起眼但在写循环判断时很容易漏掉1导致答案整体偏一位。1.3 为什么这道题的通过率不高我后来在某个讨论区里看过这道题的提交记录通过率不到三分之一。原因不是算法难而是字符串处理里的细节太多。一个初学 C 的人通常会把代码写成这样先cin word再用getline读文章结果第二行字符串是空的或者想到用find循环找结果把 tomorrow 里的 to 数了进去还有人为了让大小写不敏感把文章里的每个字符转成小写之后再找却忘了新串和原串长度相同、索引可复用这个关键点。这些坑单看每一个都很小但它们会在一个程序里同时出现。这个题目之所以经典是因为它把「字符串精确匹配」这件事拆成了一个完整的小项目输入处理、格式统一、边界判断、索引换算、多匹配计数、特殊情况输出。每一个环节出问题结果都是 WA。所以与其说是刷题不如说是在训练一种处理文本的工程思维。2. 三种常见解法对比为什么我最后选择双指针扫描2.1 直接用 split 统计次数好办位置难算很多 Python 使用者拿到这道题的第一反应是text.split()。这样确实能拿到所有单词然后count(word)就得到了出现次数。问题在于第一次出现的位置怎么算。你可以遍历 split 之后得到的单词列表找到第一个匹配项的下标再把它累加回原字符串的索引。听起来可行但实现时你要处理每段的长度、空格的数量、连续多个空格的情况。一旦文章里有连续两个空格split 之后的长度信息和原串的索引就对不上了。另外 split 还有一个隐藏问题它会吞掉文章开头和结尾的空格。如果题目要求的位置是从原串第一个字符算起那么文章开头的空格会直接影响位置计算。所以 split 方案在「统计次数」这个诉求上很顺手在「输出位置」这个诉求上却非常别扭。2.2 正则 \b 边界看似万能遇到标点就露怯正则表达式的\b被称为单词边界看起来正是为这道题准备的。用 Python 写的话就是import re matches re.findall(rf\b{word}\b, text, re.IGNORECASE) len(matches) # 出现次数但\b的边界定义和这道题的定义并不完全一致。\b判断的是字母数字与其它字符之间是否发生了切换。如果文章里出现了 dont 这种带撇号的单词\bto\b会认为 to 是独立的而题目通常只把空格当作分隔符。反过来如果目标单词包含数字或者下划线正则的边界行为也会变得和直觉不一致。更麻烦的是re.IGNORECASE这种方式在部分老版本评测环境里性能一般而且一旦文章很长正则引擎的回溯代价不小。像 P1308 这种数据范围可以到几十万字符的题目用正则虽然能跑但总让人觉得不稳。我建议把正则当作事后验证手段而不是主解法。2.3 手写双指针扫描把边界判断握在自己手里最后我选择的做法是朴素的双指针扫描从文章的开头往后走每到一个位置判断以当前位置开头、长度等于目标单词长度的子串是否满足两个条件——前一个字符是空格或不存在后一个字符是空格或不存在中间内容和目标单词完全一致。用一个生活化的类比你在一个句子中寻找一个人不能看到名字里包含某两个字就认定是他还要看他的前后是不是有区分符号。人名的边界是空格单词的边界也是空格。你手写这个逻辑时相当于把「姓名识别规则」写进了自己的代码里而不是依赖某个黑盒函数。这样做的好处有三个逻辑完全透明每一处判断你都知道为什么边界条件可以精确匹配题目约定而不是受制于正则的边界定义位置信息天然可得因为遍历的就是原字符串的索引。坏处是代码比split和正则长几行但对于一道字符串题来说这种可控性和确定性远比那几行代码更重要。3. 完整参考实现C 和 Python 的逐段拆解3.1 C 版本与关键判断逻辑下面是我最终提交的 C 版本去掉了一切花哨写法只保留核心逻辑。#include iostream #include string using namespace std; string toLower(const string s) { string res s; for (char c : res) { if (c A c Z) { c c - A a; } } return res; } int main() { string word, text; cin word; cin.ignore(); getline(cin, text); word toLower(word); text toLower(text); int lenText text.size(); int lenWord word.size(); int count 0; int firstPos -1; for (int i 0; i lenWord lenText; i) { if (i 0 text[i - 1] ! ) { continue; } if (i lenWord lenText text[i lenWord] ! ) { continue; } if (text.substr(i, lenWord) word) { count; if (firstPos -1) { firstPos i 1; } } } if (count 0) { cout -1 endl; } else { cout count firstPos endl; } return 0; }这段代码里有几个位置需要重点解释。第一个是cin word; cin.ignore(); getline(cin, text);的输入处理。cin word读取第一个单词后会在输入缓冲区里留下一个换行符如果不调用cin.ignore()把这个换行符吃掉后面的getline会直接读到空行整个程序的结果就会崩掉。我一开始就是栽在这里后面会单开一节细说。第二个是循环条件i lenWord lenText。意思是只有当当前位置开始剩余长度还够放得下完整的目标单词时才去做边界判断。这可以避免访问到字符串越界的位置。第三个是前边界判断if (i 0 text[i - 1] ! )。如果当前位置不是文章开头那么前一个字符必须是空格否则说明这个子串前面连着别的字母它只是一个更长单词的一部分直接跳过。第四个是后边界判断if (i lenWord lenText text[i lenWord] ! )。如果子串后面还有字符那么后面的字符必须是空格否则它也属于一个更长单词的一部分。第五个是firstPos i 1。因为题目要求位置从 1 开始而 C 字符串索引从 0 开始所以找到第一个匹配时要在这个索引的基础上加 1。还有一个细节是toLower函数。我在函数里直接用了字符范围判断c A c Z因为这道题的输入只包含英文字母和空格不涉及中文字符或多字节编码用简单的 ASCII 范围判断就足够了。如果你在做真实项目建议用标准库的std::tolower并转成 unsigned char但在这个判题场景里这样写更直观也能避免一些库函数在不同环境下的行为差异。3.2 Python 版本与切片比较的注意事项Python 版本逻辑一模一样但有一个地方需要特别注意不要用strip()处理第二行文章。这里给出参考代码import sys word sys.stdin.readline().strip().lower() text sys.stdin.readline().rstrip(\n).lower() len_text len(text) len_word len(word) count 0 first_pos -1 for i in range(len_text - len_word 1): if i 0 and text[i - 1] ! : continue if i len_word len_text and text[i len_word] ! : continue if text[i:i len_word] word: count 1 if first_pos -1: first_pos i 1 print(-1 if count 0 else f{count} {first_pos})第一行目标单词用strip()是安全的因为单词两边不可能有空格就算有评测数据里带了换行符strip()也能把它去掉同时不影响位置计算。第二行文章我特意用了rstrip(\n)而不是strip()。这两种处理方式的差异非常关键strip()会把文章开头和结尾的所有空白都去掉。如果文章开头恰好有空格去掉之后第一个单词在原字符串中的索引就会前移最终输出的位置会比正确答案小一位。而rstrip(\n)只去掉末尾的换行符保留文章本身的内容结构位置计算自然更可靠。Python 的切片text[i:i len_word]在子串比较时非常方便比较的其实是字节串内容。Python 切片的结束索引不包含在内所以到len_text - len_word 1为止的循环正好覆盖所有可能的位置。3.3 关于输出位置的统一约定两种语言的核心逻辑有一个共同点找到第一个匹配位置后先加 1 再输出。这个约定在 C 和 Python 里是一致的因为字符串索引都是从 0 开始。如果你看到某些题解在输出时没有加 1说明那个版本的位置定义可能从 0 开始或者他们在处理字符串边界时额外做了一些手脚。拿到一道不确定的题时建议先用一个开头就是目标单词的用例验证一下比如单词是a文章是a a a如果输出位置的第一个值是1说明你的约定对了。4. 踩坑实录从三次 WA 到一次 AC 的完整排查过程4.1 第一个坑cin 和 getline 混用导致文章读成了空串我第一次提交的代码长这样简化版string word, text; cin word; getline(cin, text);结果可想而知getline读到的text是空字符串。因为cin word在读取完单词之后输入缓冲区里还留着那个换行符getline看到换行符就认为这一行结束了直接返回空串。程序里无论执行多少个循环匹配到的次数都是 0最后只会输出 -1。排查的思路很简单在循环之前加一句调试输出打印text的长度。如果你发现长度是 0先不要往算法上想问题一定出在输入读取阶段。解决办法有三个用cin.ignore()清除缓冲区残留或者第一行也用getline读或者干脆在读取之后打印一下原串确认数据真的进来了。这个小坑看起来基础但它恰恰说明了一个问题字符串相关题目的 bug 往往不在字符串处理本身而在「数据有没有按预期进入内存」。4.2 第二个坑忽略大小写但目标单词和文章没有统一转换第二次 WA 是我自认为已经处理了大小写问题我单独写了一个toLower函数但只转换了目标单词没有转换文章。结果文章里的TO、To、tO全部匹配不上。检查过程也很直白我在toLower之后分别打印了两个字符串发现目标单词全小写文章却还是原始大小写一目了然。这个坑在真实业务里同样容易犯你在做日志关键词统计时如果日志里的关键词可能有多种大小写形式而你的查找词只转了一种统计结果必然不准。统一格式这个动作必须同时作用于「查找词」和「被查找文本」两边漏掉任何一边都不行。4.3 第三个坑没有判断单词边界把 tomorrow 里的 to 数了进去这是整个排查过程中最有价值的一次。我当时用的是text.find(word)循环查找类似这样size_t pos text.find(word); while (pos ! string::npos) { count; pos text.find(word, pos 1); }当目标单词是to文章是tomorrow to to时直接find会在索引 0 的位置找到一个to而它其实是tomorrow的前两个字母。我的错误输出会变成 3 次匹配且第一个位置是 0输出时还可能因为格式问题变成其他值。排查到这里我才真正意识到题目说的是「统计单词」而不是「统计子串」。单词和子串的区别就是那条边界线匹配到的内容前面和后面都不能是字母。我后来在代码里加上了前后空格判断再跑测试用例结果才变得正常。这个坑值得单独记下来所有「统计某个词出现次数」的需求只要文本不是用换行符严格分行你都必须自己处理边界。指望find帮你区分单词是不现实的它只关心连续字符不关心语义。4.4 第四个坑Python 的 strip() 把前导空格吞了导致位置偏移我在写 Python 版本时一开始特别顺手地写成了text sys.stdin.readline().strip().lower()。对于一个正常版本这不会出问题因为文章一般不以空格开头。但我在自测时故意加了一个前导空格的数据比如词to 文章 to be or not to bestrip()之后第一个to的索引从原本的 1 变成了 0输出的位置就变成了 1而按原字符串从 1 开始计数的定义正确答案应该是 2。这个小例子暴露了strip()的副作用它把你不想处理的字符也一起清掉了而这个字符恰恰是位置计算的一部分。改用rstrip(\n)之后前导空格被保留下来位置计算就准确了。这个经验在真实文本处理里非常重要清洗文本时用的函数必须和你的位置计算逻辑对齐否则数据的「语义位置」和「字符位置」会对不上。4.5 验证清单一组能覆盖所有边界情况的测试用例在排查完上面四个坑之后我整理了一份测试清单每次写完字符串匹配相关代码都会用这套用例自测一遍测试目的目标单词文章内容期望输出基础匹配toto be or not to be2 1大小写混用totO To TO3 1部分匹配干扰totomorrow to to2 10单词开头匹配aa b c1 1单词结尾匹配ca b c1 5完全无匹配xyza b c-1连续多个空格aa a a3 1前导空格toto be1 2最后一种情况如果题目明确文章以单词开头、不含前导空格可以忽略但在自测时保留它能让自己更清楚strip()和rstrip的区别。5. 从 P1308 到真实业务单词边界匹配能解决哪些实际问题5.1 日志关键词统计别把函数名计数数出脏数据我离开在线判题之后做过的第一个真实场景就是统计日志里某个函数被调用的次数。日志可能是这样的2025-01-01 10:00:01 INFO handleRequest from client_01 2025-01-01 10:00:02 INFO handleRequest2 from client_02 2025-01-01 10:00:03 WARN handleRequest timeout如果我想统计handleRequest这个函数名出现了多少次直接用日志字符串的count()方法handleRequest2里的那段字符也会被算进去结果就会多出很多错误数据。这时候 P1308 里学到的边界判断就直接迁移过来了匹配到handleRequest之后必须检查后面跟的是不是字母数字如果是就跳过。我在做这一步时把边界条件从「只能是空格」扩展成了「不能是字母或数字」。因为日志里函数名后面可能跟空格、冒号、括号等符号这些都应该算作边界。这个扩展只需要把text[i - 1] ! 改成!isalnum(text[i - 1])核心思路完全一致。5.2 编辑器里的「全字匹配」原来是同一套逻辑很多编辑器和 IDE 的查找功能里都有一个「全字匹配」选项你勾选之后搜索to它不会把tomorrow里的to高亮出来。这个功能和 P1308 的单词边界判断本质上是同一个东西。你去看那些编辑器处理全字匹配的源码逻辑无非就是比较目标串前后字符是不是字母数字。所以这道题刷完不只是在判题系统里多拿了一个 AC你还能理解桌面软件的一个常见功能的底层实现。以后再遇到「统计某个关键词出现次数」的需求你会自然地想到先统一大小写再做边界判断再记录位置最后处理特殊输出。这个流程已经被 P1308 完整训练过了。5.3 如果题目变复杂多维扩展其实仍然围绕边界如果题目想加大难度通常会在两个方向上做文章。第一个方向是输入范围变大文章长度从几千变成几百万substr加比较的朴素做法会容易超时。这时候可以套用 KMP 算法或字符串哈希在匹配阶段优化到 O(n m)但边界判断逻辑依然不能丢。第二个方向是分隔符变复杂从「只有空格」变成「空格、标点、换行符混合」这时候可以把边界条件从! 改成!isalnum()甚至用 Unicode 属性来判断。我在实际做文本处理时经常需要把一段几百 KB 的文章一次性读入内存然后统计某个短语的出现次数。此时getline一次只能读一行并不够用正确的做法是read全文再对全文执行边界扫描。逻辑骨架还是 P1308 那套只是读取层和边界条件需要适配真实数据格式。个人的体会是刷字符串题的时候很多人会沉醉于各种精妙的算法却忽视了最基础、也最容易出错的两个问题——数据到底怎么进来的边界条件到底是什么。P1308 的价值恰恰在这里它把一个真实世界中天天发生的需求压缩成了一道入门题你要做的不过是想清楚这两件事。如果你也卡在这道题上不妨按本文的思路先验证输入读取再统一大小写再补边界判断最后用那张测试清单自测一遍。你会发现问题其实就排着队等在那里只要一个个处理掉AC 只是时间问题。