字符串处理核心：状态机与双指针算法深度解析

1. 从“数单词”到理解字符串处理的本质最近在辅导一些刚接触编程的同学时发现一个挺有意思的现象很多人拿到“计算一行单词长度”这样的题目第一反应是去翻书找有没有现成的“单词分割函数”。这本身没错但如果你只停留在调用split()然后循环输出len()的层面那可能就错过了这道题背后更重要的东西——对输入流和字符串底层逻辑的亲手把控。这道来自《信息学奥赛一本通》的1142题表面看是简单的输入输出和字符串处理实则是训练我们“亲手拆解数据”能力的绝佳起点。它强迫你离开高级函数的舒适区去直面最原始的字符序列理解空格如何作为分隔符以及程序如何“一个字符一个字符”地构建出对数据的认知。今天我们就来彻底拆解这道题不仅给出能AC的代码更要弄明白每一步“为什么这么做”以及在这个过程中那些容易栽跟头的细节。2. 题目深度解析边界条件与核心陷阱题目描述很短“输入一行单词序列相邻单词之间由1个或多个空格间隔请对应地计算各个单词的长度。” 但这里面藏着好几个需要明确的关键点也是评判程序是否健壮的核心。2.1 输入格式的明确与“一行”的含义首先“输入一行”这个描述在编程中需要精确化。在控制台或文件输入中“一行”通常意味着以换行符\n作为结束标志的一段字符序列。对于C可能是cin配合getline对于Python就是input()。这里的关键是我们必须一次性读入整行而不是用cin stringC或input().split()Python的默认行为因为后者会自动忽略开头的空白符并以下一个空白符空格、制表符、换行作为截断点这恰恰会让我们丢失“连续多个空格”这一关键信息。所以第一步必须是读取整行。2.2 “单词”的定义与分隔符的处理题目说“相邻单词之间由1个或多个空格间隔”。这意味着分隔符唯一只有空格 是分隔符不包括制表符\t或其他空白字符。这是一个简化但在严格的在线评测OJ环境下我们必须严格按照题意来。空格数量不定可能是1个也可能是多个。这直接否决了用“遇到一个空格就切分”的简单逻辑因为多个连续空格会产生空字符串片段这些片段不是单词必须被跳过。开头和结尾可能有空格输入的行开头和结尾也可能有空格。这些空格不构成单词在计算时必须被忽略。这是最常见的陷阱之一很多人的程序在遇到 hello world 这样的输入时就会出错。2.3 输出格式的精确对应“对应地计算各个单词的长度”意味着输出顺序必须与单词在输入行中出现的顺序严格一致。输出通常是以空格分隔的每个单词的长度。如果一行没有单词例如输入全是空格根据常规逻辑应该没有输出或者输出一个空行。这些细节需要在编码前就想清楚。3. 核心算法设计状态机与双指针法解决这类问题有两种主流的底层思想状态机State Machine和双指针Two Pointers。它们都不依赖于高级的字符串分割函数能让我们更透彻地理解过程。3.1 状态机思路清晰地刻画程序“思维”我们可以把程序读取字符的过程看作是在几个状态间切换状态0寻找单词开始初始状态。程序逐个读取字符如果遇到非空格字符说明找到了一个单词的开头记录当前位置并切换到状态1。状态1记录单词中。继续读取字符只要不是空格就认为字符属于当前单词持续累加长度或记录位置。一旦遇到空格说明当前单词结束输出其长度然后切换回状态0。这个思路逻辑非常清晰尤其适合用while循环和if-else来实现。它明确区分了“在单词外”和“在单词内”两种情形不容易出错。C状态机实现示例#include iostream #include string using namespace std; int main() { string line; getline(cin, line); // 读取整行 int n line.length(); int i 0; bool inWord false; // 状态标志是否处于单词内 int wordLen 0; while (i n) { if (line[i] ! ) { // 当前字符不是空格 if (!inWord) { // 如果之前不在单词内说明是单词开头 inWord true; wordLen 1; // 开始计数 } else { // 已经在单词内继续计数 wordLen; } } else { // 当前字符是空格 if (inWord) { // 如果之前是在单词内说明单词结束了 cout wordLen ; inWord false; wordLen 0; } // 如果之前就不在单词内说明是连续空格直接跳过 } i; } // 循环结束后检查是否最后一个字符是单词结尾即行末没有空格结尾 if (inWord) { cout wordLen; } return 0; }3.2 双指针思路高效定位单词边界双指针法更直观一些。我们用两个“指针”通常是整数索引i和j来在字符串上滑动。指针i负责寻找单词的起始位置。它不断向前移动跳过所有的空格直到指向一个非空格字符。此时i的位置就是单词的开始。指针j从i开始寻找单词的结束位置。它继续向前移动只要指向的不是空格就继续移动。当j指向空格或字符串末尾时j-1的位置就是单词的结束。计算单词长度j - i。输出长度后将i移动到j的位置即空格处然后重复步骤1开始寻找下一个单词。这种方法代码紧凑效率高是竞赛中的常用技巧。Python双指针实现示例line input().rstrip(\n) # 读取整行并去掉末尾可能的换行符input()通常已处理但更安全 n len(line) i 0 first_output True # 用于控制输出空格使格式更美观 while i n: # 阶段1跳过前导空格和单词间的多个空格 while i n and line[i] : i 1 if i n: # 如果跳完空格已经到字符串末尾说明没有单词了 break # 此时 line[i] 是非空格字符即单词开始 start i # 阶段2找到这个单词的结尾 while i n and line[i] ! : i 1 # 此时 i 指向了单词后的第一个空格或字符串末尾 word_len i - start if not first_output: print( , end) print(word_len, end) first_output False # 循环结束所有单词长度已输出。如果一行没有单词则无输出。 print() # 最后输出一个换行符合多数OJ的格式要求注意上面Python示例中使用了first_output标志来控制输出格式避免了末尾多一个空格。有些OJ系统对末尾空格不敏感但养成输出整洁的习惯总是好的。更简单的做法是用列表先存储结果最后用print(*length_list)一次性输出。4. 不同语言下的实现策略与避坑指南虽然算法思想通用但在不同编程语言中实现细节和可利用的工具库不同也会产生不同的“坑”。4.1 C/C 实现注重手动控制与效率对于C/C选手这道题是练习字符数组C风格字符串和string类操作的经典题。坑点1输入整行C风格用fgets(char_array, sizeof(char_array), stdin)。注意它会读入换行符\n处理时需要判断。C风格用getline(cin, str)。这是最推荐的方式简单安全。坑点2遍历与边界手动遍历时务必注意数组下标不要越界。在双指针法中内层while循环的条件i n至关重要。坑点3输出格式C中连续用cout len ;输出最后会多一个空格。虽然很多OJ接受但严格的题目可能判错。可以采用类似Python中的“首次输出”技巧。一个健壮的C双指针实现#include iostream #include string using namespace std; int main() { string s; getline(cin, s); int n s.size(); int i 0; bool isFirst true; // 是否是第一个输出的数字 while (i n) { // 跳过空格 while (i n s[i] ) i; if (i n) break; // 跳过空格后到末尾结束 // 找到单词结束位置 int j i; while (j n s[j] ! ) j; // 计算并输出长度 if (!isFirst) cout ; cout (j - i); isFirst false; i j; // i跳到当前单词结束的位置即空格处外层循环的i会使其进入下一个循环 } cout endl; // 输出换行 return 0; }4.2 Python 实现简洁背后的陷阱Python让这道题变得极其简单但正因为简单更容易忽略细节。“一行代码”的诱惑与问题print(*[len(w) for w in input().split()])这行代码利用了input()读取一行split()默认以任意空白字符空格、换行、制表符等分割并自动过滤掉空字符串列表推导式计算长度最后用*解包打印。对于本题它完全正确且优雅。因为题目明确分隔符是空格split()的行为完全符合要求。但是这里存在一个教学上的“陷阱”如果你只记住了这行代码而没有理解split()在没有参数和有参数时的区别下次遇到“以逗号分隔”或者“严格以单个空格分隔需保留空单词”的题目时就会出错。s.split(): 按任意空白字符分割并自动移除结果中的空字符串。s.split( ): 严格按单个空格字符分割。如果存在连续空格会产生空字符串。所以更严谨的教学代码应该这样写以明确意图line input() # 明确使用空格作为分隔符但这样会得到空字符串片段 parts line.split( ) # 因此需要过滤掉空字符串 words [part for part in parts if part ! ] # 再计算长度 lengths [len(word) for word in words] print(*lengths)虽然最终结果和split()一样但这个过程清晰地展示了“分割-过滤-计算”的步骤加深了对字符串处理的理解。4.3 其他语言如Java的注意点Java中常用的Scanner.nextLine()读取整行然后用line.split( )可以按一个或多个空格进行正则分割但同样要注意开头结尾的空格会导致空字符串。更稳健的做法是使用line.trim().split(\\s)先去掉首尾空格再按空白字符分割。但trim()可能会误伤首尾的非空格字符本题不会所以最根本的还是手动遍历或使用StringTokenizer类虽然已过时但思路清晰。5. 测试用例设计与调试技巧写出代码不算完能否通过所有边界情况的测试才是关键。自己设计测试用例是一个优秀程序员必备的习惯。针对本题必须设计以下几类测试用例普通情况hello world-5 5多个连续空格hello world-5 5开头有空格 hello world-5 5结尾有空格hello world -5 5首尾都有空格 hello world -5 5单个单词programming-11单个单词带空格 programming -11空行或纯空格或 - 无输出或输出一个空行长单词与短单词混合a bc def ghij-1 2 3 4调试技巧打印中间变量在状态机或双指针算法中在关键步骤后打印i,j,inWord,wordLen等变量的值观察其变化是否符合预期。可视化遍历在纸上画出字符串手动模拟你的算法用笔移动i和j指针这是理解算法最有效的方式。使用在线调试器如果环境允许使用IDE的调试功能单步执行观察变量和程序流程。6. 从本题延伸的常见变体与解题思路掌握了本题的核心可以轻松解决一系列变体问题这也是刷题举一反三的关键。变体1统计单词个数而非长度。这更简单只需要在发现一个单词开始时状态机中!inWord变为true或双指针中找到start时计数器加1即可。变体2以特定单个字符如逗号分隔。这时分隔符不是空格了。算法完全一样只需把判断条件从line[i] ! 改为line[i] ! ,。但要注意如果用split(,)连续逗号会产生空字符串需要根据题目要求决定是否保留。变体3分隔符是多种字符如空格、逗号、句号。此时判断“是否分隔符”的条件变成一个集合检查。例如if (delimiters.find(line[i]) string::npos)C或者if line[i] not in ,.Python。核心算法框架不变。变体4不仅输出长度还要输出单词本身。在记录长度的同时用substr(start, length)C或切片line[start:end]Python把单词子串也保存下来即可。变体5输入包含多行直到文件结束EOF。这是OJ常见格式。需要将整个读取和处理的逻辑包在一个while (getline(cin, line))或for line in sys.stdin:的循环里。每行独立处理输出各自的结果。通过这样一道看似简单的题目我们实际上深入探讨了字符串处理的基石输入缓冲、字符遍历、状态管理、边界条件处理。这才是学习算法和编程的正确姿势——不满足于AC而要理解每一行代码背后的“所以然”。下次再遇到字符串处理问题不妨先想想我的指针应该怎么走程序现在处于什么状态