说实话字符串处理是我刷题以来最不容易翻车、但最容易马虎的一类题。最近在整理基础算法的时候又看到一道很经典的入门题题目背景是这样小r正在学习字符串处理小x给了他一个字符串s要找出这个字符串里最长的一段相同字符串。说白了就是在一串字符里找到连续相同字符组成的最长片段返回它的长度。解决这类题目的关键不是背模板而是真正理解“连续相同”四个字背后的扫描逻辑。本文就围绕这道最长相同字符串题把思路拆解、代码实现、边界测试和常见坑一次讲透特别适合刚开始刷字符串处理题的初学者参考。1. 先把题目读懂最长相同字符串到底要找什么1.1 先别急着写代码把“相同字符串”的定义确认清楚这个题目看起来简单但“最长相同字符串”这几个字在不同题目里可能指完全不同的东西写代码之前一定要先确认清楚。常见的理解有三种第一种也是绝大多数入门题采用的在一个字符串内部找由连续相同字符组成的最长子串。比如aaabbcccc这个串最长的一段就是cccc长度是 4。题目背景里“小x给了小r一个字符串s”大概率说的就是这种。第二种是两个字符串之间的“最长公共子串”。这种题一般会给你两个串问它们的公共部分最长是多少解法通常是动态规划难度比本题高一个档次。从题面“小 r 正在学习字符串处理”这种新手视角来看一上来就考 LCS 的可能性不算高但如果你在OJ上看到题目描述里出现“两个字符串”字样就要把它和本题区分开。第三种统计整个字符串中某个字符出现的总次数然后输出最大值。注意这和“连续相同”是完全不同的概念。比如aabbaaaa字符a出现了 6 次但最长连续相同段只有 4 个a连在一起。如果题目要你输出 6那是哈希表统计如果要你输出 4才是本文讲的连续段扫描。所以拿到题目第一步不是打开编译器而是先找两个东西样例输入输出以及数据范围。样例能告诉你题目的真实意图数据范围能告诉你该用 O(n²) 还是必须 O(n)。1.2 暴力解法为什么能过但没必要很多新手第一反应是暴力枚举所有子串的起点和终点再检查这一段里的字符是否全部相同。这样做的复杂度是 O(n³)如果字符串长度到 10000基本就卡死了。稍微优化一下枚举起点 i然后从 i 开始往右扩展直到遇到第一个与 s[i] 不同的字符为止记录这一段长度。这样复杂度降到 O(n²)思路非常简单用来验证题意、对拍测试是完全够用的。但题目如果给到 10^5 甚至 10^6 级别的字符串O(n²) 必定超时。对于最长相同字符串这种题目真正的考点就一个你能不能想到用一趟线性扫描解决问题。2. 核心思路一趟循环找出最长连续相同段2.1 相邻比较法的每一步核心结论其实一句话一段区间内所有字符相同当且仅当这段区间内每个相邻字符对都相等。比如aaaa因为s[1]s[0]、s[2]s[1]、s[3]s[2]所以整体相等。反过来只要出现一对相邻字符不同这段就断开了。基于这个性质我们从左到右扫一遍维护两个变量curLen当前正在统计的这一段连续相同字符的长度maxLen目前为止见过的最大段长。初始化时curLen 1因为第一个字符自己就是一段。maxLen 1除非字符串为空。然后从i 1开始遍历如果s[i] s[i-1]说明当前字符和上一个字符相同当前段还没断curLen如果s[i] ! s[i-1]说明上一段在这里结束先用curLen去更新maxLen然后把curLen重置为 1代表s[i]这一个字符构成了新的一段。有个细节特别容易漏循环结束后还要再更新一次maxLen。因为最长的一段可能正好在字符串末尾比如aaabbcccc里最长段是末尾的cccc如果循环内只在遇到不同字符时才更新遍历结束后这部分长度就永远不会被记录。2.2 双指针写法把解法写成区间扫描除了相邻比较法双指针也是这道题的经典写法而且在我看来更符合“连续段”这个直观概念。外层用一个指针 i 表示当前段的起点内层用一个指针 j 从 i 开始向后扫描直到遇到第一个与s[i]不同的字符。那么j - i就是从 i 开始的连续相同段的长度。更新完maxLen后直接把 i 跳到 j 的位置继续处理下一段。这种写法的好处是代码逻辑和“段”的概念一一对应不容易漏掉末尾结算。坏处是如果字符串特别长内层循环的总执行次数依然是 O(n)因为每个字符只会被访问一次不会产生额外开销。我实际写题的时候两种写法都会用代码量优先用相邻比较法想表达过程清晰就用双指针。考试和面试中双指针更容易向别人讲明白思路。2.3 时间复杂度和空间复杂度无论是相邻比较法还是双指针都只需要线性扫描一遍字符串时间复杂度是 O(n)。空间上只需要几个整型变量额外空间是 O(1)不依赖字符串长度。这里可以提一个性能细节由于我们是从左往右顺序访问字符串的每个字符内存访问模式非常规整和缓存命中的规律高度吻合。在数据量很大的场景下这种顺序扫描的速度会比频繁跳跃访问快得多。所以哪怕 O(n) 算法内部常数有点差别整体也不会差到哪里去。3. 完整代码与实现细节C为主Python参考3.1 最通用的 C 写法下面是完整的 C 实现我加了多组输入支持很多学校的 OJ 或者新生赛的题目都会用多组测试数据来卡人。#include iostream #include string #include algorithm using namespace std; int main() { string s; while (cin s) { if (s.empty()) { cout 0 endl; continue; } int curLen 1; int maxLen 1; for (int i 1; i (int)s.size(); i) { if (s[i] s[i - 1]) { curLen; } else { maxLen max(maxLen, curLen); curLen 1; } } // 关键处理最长段在字符串末尾的情况 maxLen max(maxLen, curLen); cout maxLen endl; } return 0; }这里有几个值得注意的写法习惯for (int i 1; i (int)s.size(); i)我特意把s.size()强制转换成int。因为size()返回的是size_t类型属于无符号整数如果你写成i s.size() - 1当字符串长度为 0 时s.size() - 1会变成极大的正数导致循环完全失控。这是一个非常经典的无符号数下溢坑新手经常在这里翻车。maxLen初始值是 1 而不是 0理由很简单只要字符串非空最长相同段的长度至少是 1。如果初始化成 0遇到a这种单字符输入时逻辑上需要额外的判断才能得出正确答案。我习惯直接把初始值定为 1减少一次特判。3.2 三种常见变体空白字符、多行输入、输出子串本身上面代码用的是cin s它会自动跳过空白字符适合题目输入里不包含空格的字符串。但有些场景会遇到特殊情况需要改写法。如果字符串里可能包含空格比如输入一个句子让你找连续相同字符那cin s就不行了它会读到空格就停下来。这时候要用getlinestring line; getline(cin, line); // 处理 line注意 line 可能为空如果题目不保证只有一组数据while (getline(cin, line))也是一个稳妥的处理框架。如果题目不只需要长度还要你输出最长的那段子串本身就需要额外记录起止位置。做法是加两个变量bestStart和bestLen每当发现更长的段时更新它们if (curLen maxLen) { maxLen curLen; bestStart i - curLen 1; }循环结束后s.substr(bestStart, maxLen)就是最长相同子串。3.3 Python版本Python 代码更短适合用来快速验证思路s input().strip() if not s: print(0) else: cur_len, max_len 1, 1 for i in range(1, len(s)): if s[i] s[i - 1]: cur_len 1 else: max_len max(max_len, cur_len) cur_len 1 max_len max(max_len, cur_len) print(max_len)如果题目有多组输入可以改成按行循环处理。Python 里len(s)本身是 int 类型不会像 C 那样踩无符号数坑但边界逻辑和 C 完全一致同样要注意最后再更新一次maxLen。4. 边界条件与测试用例OJ判题不通过的常见原因4.1 六类必测数据这道题的代码逻辑虽然简短但边界条件非常多稍不留神就会在某个奇怪的数据上翻车。我刷题时有一个习惯不管什么题先把边界测试集写出来再开始写实现逻辑。下面是本题的六类必测数据每一类我都用表格整理好了。输入期望输出测试目的空字符串0最容易被忽略的边界a1单字符字符串aaa3整个字符串就是一个最长段aaabbcccc4最长段出现在末尾考验循环结束后的结算abc1所有段长度都是1没有任何连续相同aabbcc2多个段长度相同考验最大值更新逻辑空字符串这个点用cin s的时候通常读不进来空串但如果用getline读一整行空行就完全有可能出现。所以我写代码时总是保留对空串的处理成本很低却能避免一个隐性隐患。aaabbcccc是这道题最经典的测试数据它能同时覆盖“中间段长度变化”和“末尾段最长”两个关键场景。我之前给学弟学妹讲这题的时候永远先用这一组数据走一遍完整流程。4.2 如何自己构造测试用例很多新手不知道拿到题之后怎么验证自己的代码除了题目给的样例以外一无所知。我的做法是写完一个版本后马上写一个暴力版然后自己造随机数据对拍。对拍的基本套路是这样的写一个暴力函数枚举所有起点向右扩展到第一个不同字符复杂度 O(n²)但逻辑极其直观写一个快速函数就是上面讲的 O(n) 版本用随机生成器生成大量随机字符串长度从 1 到 50 不等字符集限制在ab或abc之间把两组结果逐一比较一旦出现不一致就说明某个版本有 bug。在竞赛环境里这种对拍方式能帮你揪出几乎所有逻辑错误。我现在做字符串相关的题目已经养成了条件反射只要时间复杂度允许写完正解必写暴力对拍宁可多花五分钟也不愿意提交上去 WA 一发再回来找问题。5. 常见错误与排查技巧速查表5.1 六类高频错误这道题我见过太多人踩坑大部分错误都是高度雷同的我直接整理成一张速查表方便你对照自己的代码排查。错误现象根本原因解决方法输入aaa输出 1循环结束后没有结算最后一组连续段在循环外再加一次maxLen max(maxLen, curLen)输入空串时程序异常没有对s.empty()做特判初始化时访问s[0]读取后立即判断空串i s.size() - 1循环次数诡异size()是无符号数空串时下溢转成int或先取int n s.size()输出结果整体偏大把“字符总出现次数”和“连续相同长度”搞混回看题目描述确认是不是要求连续子串输入aabbaaaa输出 6用哈希表统计字符频率而不是扫描连续段换回相邻比较法题目要求输出子串却输出了长度只维护了maxLen没有记录起点位置增加bestStart记录其中第二个和第五个是新手最常犯的。空串问题是典型的边界意识不足字符频率混淆是对题意的理解偏差这两类问题在字符串处理入门阶段出现的频率几乎一样高。5.2 一套通用排查顺序万一你的代码提交后还是 WA我建议按下面这个顺序排查能省不少时间先看输出格式。OJ 对输出换行、行尾空格都非常敏感有时候你逻辑全对只是因为多输出一个空格被判 WA这种问题肉眼很难发现。再看边界数据。拿第 4 节那张表里的数据逐条跑一遍多数逻辑错误都能暴露出来。如果你的代码能正确处理空串、单字符、最长段在末尾这三个点基本就稳了一大半。最后做随机对拍。如果手头有暴力版本就随机生成几千组数据对比。如果没有也可以用题目的样例和自己构造的极端数据交叉验证。这套排查顺序适用于几乎所有单串处理题不局限于最长相同字符串这一道后面可以一直复用。6. 延伸思考从这道题看字符串处理的通用套路6.1 与数据压缩RLE的关系最长相同字符串的扫描方式其实和一种非常古老的压缩算法——游程编码Run-Length EncodingRLE是完全一致的。RLE 的思想很简单把连续出现的相同字符记成一个二元组(字符, 出现次数)。比如aaabbcccc压缩后就是a3b2c4。你去写一个 RLE 压缩函数就会发现它的核心代码和本题几乎一模一样唯一区别在于RLE 要求输出每一段的字符和长度而本题只需要输出最大长度。所以这道题学扎实了等于是顺手掌握了 RLE 的核心扫描逻辑。以后遇到类似的压缩类问题你会马上反应过来这不就是把连续段找出来吗我建议刷完本题之后自己主动加一个小需求——输出每个连续段的字符和长度把代码改把短彻底消化这个套路。6.2 由“拼数(number)”看字符串排序关于热搜词里出现的“拼数(number)”它其实也是字符串处理极好的延伸练习。题目大概意思是给你若干个正整数要求把它们拼接成一个最大的数。例如数字[3, 30, 34, 5, 9]可以拼成9534330。这题的常规解法非常反直觉先把整数转换成字符串然后按照a b b a的规则排序再依次拼接。这里a b不是数值相加而是字符串拼接。比较两个数字谁应该排在前面不是看数值本身而是看两种拼接结果谁更大。bool cmp(const string a, const string b) { return a b b a; }它和最长相同字符串的共同点在于都是通过修改“比较规则”来简化问题。本题中我们判断相邻字符是否相等来决定段的起止拼数题中我们通过比较拼接结果来决定排序顺序。字符串处理题里这种“自定义比较/自定义分段规则”的思路非常常见值得专门训练。6.3 通用自测方法论最后再说一点我自己总结的方法论。字符串处理题和纯计算题有个很大的区别字符串的可读性比较强随手就能构造出很多测试数据。所以不要只会跑题目给的样例要主动去构造极端场景。构造测试时重点关注四个维度长度极端空、1、超长、重复模式全相同、全不同、周期性重复、段长分布最长段在开头、中间、末尾、字符集全小写、大小写混合、含数字。把这四个维度组合一下就能形成一套覆盖面很全的测试用例库。我现在做任何字符串题第一步都是先在心里过一遍这几个极端场景确认思路不会出边界问题之后才会动键盘。这个习惯是从写最长相同字符串这种基础题开始养成的后来做字符串哈希、KMP、后缀数组这些更复杂的算法题时同样受益无穷。结语我个人实际操作中的体会是这种入门级字符串处理题真正值钱的地方不在于“会写”那十行代码而在于通过它建立起对连续段的直觉、对边界条件的敏感、对测试用例的规划能力。建议你至少手写三遍一遍相邻比较法、一遍双指针、一遍 RLE 扩展版本。写完这三个版本输入aaabbcccc的时候你脑子里应该已经能自动演绎出整个扫描过程。刷题不是比谁 AC 得多而是比谁把基础题吃得更透。