讲一个刷题时特别容易懵的场景拿到一道题标题写着“最长相同字符串”打开题目描述一看是“给一个字符串 s求……”——你脑子里第一时间冒出来的可能是“最长连续相同字符”也可能是“最长公共前缀”还可能是“最长重复子串”。这三种东西在中文题面里都能被叫成“最长相同字符串”字符串处理这个领域里概念撞车特别频繁挂着同一个名字判题逻辑却差了十万八千里。这篇文章就把“最长相同字符串”这条线彻底拆开从最常见的长连续相同字符段讲起过渡到两个串的最长公共前缀再上升到单串的最长重复子串最后用一个“拼数(number)”场景下的变体题收尾。无论你是在准备算法竞赛、应付面试手撕代码还是想系统补一下字符串处理的基础跟着敲一遍比单纯背模板有用得多。1. 先看清题目同样是“最长相同字符串”问法差得远字符串处理题最烦人的不是算法难而是题面表述不精确。特别是“最长相同字符串”这种说法在不同的 OJ 和面试场合里至少对应三种完全不同的模型。1.1 三种最容易撞车的解读第一种是最直观的在一个字符串里找最长的连续相同字符段。比如aaabbbbcccc最长连续相同字符段是bbbb或cccc长度为 4。这类题的典型问法是“求最长的连续相同字符子串长度”它考察的是线性扫描和贪心维护状态。第二种是两个字符串的最长公共前缀LCP。比如abcdxxx和abceee它们的最长公共前缀是abc长度 3。这类题通常出现在需要“快速比较两个字符串前段是否一致”的场景比如字典序比较、字符串排序、拼接后去重。第三种是单个字符串内部的最长重复子串。比如banana里ana出现了两次na也出现了两次最长重复子串就是ana长度 3。注意这里的“重复”允许子串互相重叠它和“连续相同字符”完全不是一回事——banana里连续相同字符段只有一个字符但最长重复子串长度是 3。这三种模型处理方式完全不同先搞清楚题目到底要哪个否则后面写出来的代码都是白搭。我的习惯是拿到题先画一个具体的例子把“目标输出”确定下来再开始想算法。你要是愿意也可以用题目给的样例去试多试两次就理解题面了。1.2 从“拼数(number)”看这类题的真实场景题目描述里出现“小 r 正在学习字符串处理小 x 给了小 r 一个字符串 s”这个开场在竞赛题里太常见了。特别是“拼数(number)”这个名字我猜本质上是把若干数字片段拼成一个长串然后再做字符串处理。数字串本身也是字符串9和9之间照样可以做相等比较。这类题的真实场景往往不是让你“纯求一个最长段”而是把它藏在某个游戏规则或拼接逻辑里。比如给你几个数字串拼接成一个大串求大串里的最长连续相同段给你一个很长的数字密码串找出现次数最多的长度为 k 的子串把两个数字串做拼接在拼接处可能产生新的连续相同段。标题里带个“number”大概率是强调“输入是数字字符串别当成整数去算”。数字字符和普通字符在处理上没有任何区别但有一个心理陷阱你会下意识想把数字串转换成整数一旦转成整数前导零、位数、拼接方式全乱了。字符串处理题的第一原则就是——题目说给字符串就老老实实按字符串处理。1.3 先建模再动手不管题目是哪种变体我都建议先做两步确定“相同”的定义是比较单个字符相等还是比较一整段子串相等确定“最长”的范围是全局一段还是任意两段之间还是前缀关系。把这两点想清楚再往下选算法。下面我会按“基础 → 进阶 → 拔高”的顺序把三种核心模型的完整代码和推导逻辑都过一遍。每个模型我都会给出可以直接抄的模板以及我在实际写题时踩过的坑。2. 最长连续相同字符一行扫描就够了这是“最长相同字符串”最朴素的形态也是很多新手最容易想复杂的一道题。给定字符串s比如abbbccda要输出3因为bbb连续出现 3 次。很多人的第一反应是用哈希表统计每个字符出现次数然后取最大值——这是一个经典的错误思路因为题目要求“连续”而哈希表只统计出现次数不关心位置关系。2.1 核心状态设计正确做法是维护两个变量cur_len当前连续相同字符段的长度best_len到目前为止见过的最大连续相同字符段长度。从左往右扫一遍每次比较当前字符和前一个字符是否相同。相同就把cur_len加一不同就说明前一个连续段结束了把cur_len重置为 1因为当前字符是新的连续段的起点。每一步都用cur_len去更新best_len。整个过程只用一次遍历时间复杂度 O(n)空间复杂度 O(1)。这个思路本质上是一种贪心它只关心“当前这一段还能不能延续”完全不关心之前已经扫过的部分因此不需要回头重扫。2.2 完整实现与输出子串如果题目只要求返回长度代码长这样def longest_same_run_length(s: str) - int: if not s: return 0 cur_len 1 best_len 1 for i in range(1, len(s)): if s[i] s[i - 1]: cur_len 1 else: cur_len 1 if cur_len best_len: best_len cur_len return best_len很多题不会只给一个int结果还可能要求你输出最长连续相同子串本身、起点下标、终点下标。这时候需要在扫描过程中额外记录best_start和best_lendef longest_same_run(s: str) - tuple[int, str]: n len(s) if n 0: return 0, best_len 1 best_start 0 cur_len 1 cur_start 0 for i in range(1, n): if s[i] s[i - 1]: cur_len 1 else: cur_len 1 cur_start i if cur_len best_len: best_len cur_len best_start cur_start return best_len, s[best_start:best_start best_len]注意一个细节s[best_start:best_start best_len]切出来的子串长度正好是best_len因为虚拟下标从best_start到best_start best_len - 1左闭右开切片要写成best_start best_len。这个小地方我踩过不止一次经常切出来的子串多一位或少一位。2.3 边界条件与性能分析空串返回 0单字符字符串返回 1 而不是 0——这个坑特别隐蔽很多新手会在cur_len初始化为 0导致a返回 0。实际上任何非空字符串的连续相同段长度至少是 1。这个模型还有一个变体求“删除最多 k 个字符后最长连续相同段长度”。这是滑动窗口双指针的经典应用本质上就是在窗口内维护每个字符出现次数保证窗口内除了主导字符外其他字符不超过 k 个。这类题目在面试题里出现频率极高思路还是这个扫描框架只是窗口右端和左端都要移动。实测下来这个扫描在 Python 里处理 10^6 长度的字符串也就是零点零几秒的量级完全不需要任何优化手段。如果题目给的是一组字符串要求对每个字符串都求一遍最长连续段那也只用逐个调用这个函数即可仍然线性。3. 两个串的最长公共前缀从暴力到哈希二分下一类常被叫“最长相同字符串”的题是给定两个字符串找它们从开头开始有多少位完全相同也就是最长公共前缀 LCP。假设有s engineeringt element从第一个字符e开始逐位比对可以看到e、l、e相同到第四位n和m不同所以 LCP 长度为 3。3.1 暴力逐位比较为什么其实不差逐位比较的思路非常直白def lcp_brute(s: str, t: str) - int: i 0 while i min(len(s), len(t)) and s[i] t[i]: i 1 return i这个版本的复杂度是 O(min(n, m))。严格来说是 O(答案长度)因为一旦遇到不相等字符就提前退出。对于“单次查询”场景这个算法其实是最优的——你至少得看这么多字符才能确定前缀到哪里结束任何算法都无法跳过这些比较。很多人一听到 LCP 就想着上字符串哈希、二分、后缀数组反而把简单问题搞复杂了。暴力法在这个场景下不需要被优化。但麻烦的是“多次查询”场景。比如给你一堆字符串任意给出两个下标要求快速回答它们之间的 LCP。逐位比较最坏会退化到 O(长串长度)查询次数一多就爆炸。这时候才需要预处理。3.2 多次查询用哈希预处理字符串哈希的思路是把一个字符串映射成一个整数或一组整数这样比较两个子串是否相等就不再逐个字符比较而是比较两个整数是否相等直接把比较复杂度降到 O(1)。常用的哈希构造方式是滚动哈希把字符串看成是一个 base 进制的大整数其中 base 取一个大于字符集大小的质数比如 131。对于字符串s前缀哈希数组h[i]表示s[0:i]这个前缀的哈希值。递推公式h[i 1] h[i] * base ord(s[i])如果想取出任意区间[l, r)的子串哈希就用h[r] - h[l] * base^(r - l)。这里需要预计算base的幂次数组p[i] base^i。完整模板def build_hash(s: str): base 131 mod 1_000_000_007 n len(s) h [0] * (n 1) p [1] * (n 1) for i, ch in enumerate(s): p[i 1] p[i] * base % mod h[i 1] (h[i] * base ord(ch)) % mod return h, p, base, mod def get_hash(h, p, mod, l, r): # 返回 s[l:r] 的哈希值左闭右开 return (h[r] - h[l] * p[r - l]) % mod这里有个 Python 细节(h[r] - h[l] * p[r - l]) % mod在 Python 中一定会返回非负值因为 Python 的取模运算结果总是和除数同号所以负数取模会得到正确范围内的正值不会出错。但在 C 里同样写法可能得到负数需要额外加一次mod再取模。有了哈希数组求两个字符串的 LCP 就可以配合二分来做二分长度mid检查两个字符串各自的前mid个字符的哈希值是否相等。如果相等说明前缀长度至少是mid往大了试如果不相等往小了试。def lcp_by_hash(s: str, t: str) - int: hs, ps, bs, ms build_hash(s) ht, pt, bt, mt build_hash(t) lo, hi 0, min(len(s), len(t)) while lo hi: mid (lo hi 1) // 2 if get_hash(hs, ps, ms, 0, mid) get_hash(ht, pt, mt, 0, mid): lo mid else: hi mid - 1 return lo二分的上下界很明确下界 0上界是两个串长度的较小值。每次判定 O(1)整体一次查询 O(log n)。和暴力法相比单次查询反而更慢但如果查询次数很多预处理的 O(n) 摊下来就非常划算。这类“以空间换时间”的思路在字符串处理里极其常见。3.3 哈希构造里的两个关键选择第一个选择是base的取值。理论上只要不能整除 mod任何大于字符集大小的值都可以但实际建议用 131、13331、13131 这类质数原因在于减少哈希冲突。字符集如果只考虑 ASCII26 个字母那 base 至少要大于 26如果会有中文或其他 Unicode最好用更大的 base比如 13131。第二个选择是 mod 的取值。常见取10**9 7或998244353这两个都是大质数在竞赛里被验证过很多次。我自己更常用10**9 7因为它足够大哈希值分布比较分散碰撞概率低。但如果数据量到 10^6 级别单模数可能还是存在理论上的碰撞风险后面第 6 节我会讲双哈希的对策。4. 单串的最长重复子串哈希二分是性价比之王第三种“最长相同字符串”是求单个字符串内部重复出现的最长子串也就是最长重复子串。这是很多面试题的升级版本也是最能体现“会建模”和“只会背模板”差距的一道题。4.1 暴力枚举的瓶颈在哪里最直观的做法是枚举所有起点对(i, j)然后求从这两个位置开始的后缀的 LCP取最大值。比如s banana枚举(1, 3)对应anana和anaLCP 是ana长度 3这就是答案。枚举起点对是 O(n^2) 的求两段后缀的 LCP 最坏又是 O(n)总的复杂度高达 O(n^3)。即便优化成从后往前动态规划dp[i][j] dp[i1][j1] 1 (s[i] s[j]) dp[i][j] 0 (s[i] ! s[j])把复杂度降到 O(n^2)空间 O(n^2)但当 n 到 10^5 甚至 10^6 时仍然不可接受内存直接爆掉。竞赛和面试里n 稍微大一点就必须换思路。4.2 二分长度 哈希查重核心洞察是如果一个长度为 L 的子串重复出现了那么长度小于 L 的子串也一定会重复出现反过来如果所有长度为 L 的子串都不重复那么更长的一定更不重复。也就是说重复子串的存在性关于长度是单调的。有单调性就能二分。于是问题转化为一个子问题判断字符串中是否存在长度为 L 的重复子串。做法如下从位置 0 到n - L依次取出长度为 L 的子串计算哈希值把哈希值存入set如果某个哈希值已经出现过说明存在长度为 L 的重复子串返回 True。整个过程 O(n)配合外层二分 O(log n)总复杂度 O(n log n)。这是一套在很多字符串问题里都能复用的框架。用哈希值查重有个隐患哈希碰撞可能导致两个不同子串被误判为相同。为了规避碰撞我习惯在哈希值相同的时候再去比较一下原始字符串是否真的一致。这样即使单模数碰撞了最终结果仍然正确只是偶尔多一次 O(L) 的字符串比对而已。代码如下def build_hash(s: str): base 131 mod 1_000_000_007 n len(s) h [0] * (n 1) p [1] * (n 1) for i, ch in enumerate(s): p[i 1] p[i] * base % mod h[i 1] (h[i] * base ord(ch)) % mod return h, p, base, mod def get_hash(h, p, mod, l, r): return (h[r] - h[l] * p[r - l]) % mod def find_duplicate_substr(s: str, L: int): n len(s) h, p, base, mod build_hash(s) seen {} for i in range(n - L 1): val get_hash(h, p, mod, i, i L) if val in seen: j seen[val] if s[j:j L] s[i:i L]: return s[i:i L] else: seen[val] i return None def longest_repeat_substr(s: str) - str: lo, hi 1, len(s) ans while lo hi: mid (lo hi) // 2 sub find_duplicate_substr(s, mid) if sub is not None: ans sub # 当前长度可行记录答案并尝试更长的 lo mid 1 else: hi mid - 1 # 当前长度不可行缩短 return ans注意二分写法的细节。我用lo hi配合mid (lo hi) // 2如果可行就记录答案、lo mid 1不可行就hi mid - 1。这个写法可以正确找到“最大可行长度”并且最终答案保存在ans里不会因为最后一次失败尝试而被清空。4.3 输出最长重复子串的位置和次数有些题还会进一步要求输出最长重复子串的出现次数、第一次出现的位置。只需要把find_duplicate_substr里的字典从“哈希值 - 下标”改成“哈希值 - 下标列表”每次遇到相同哈希值时记录一次出现。选择第一次出现的位置时取最小的下标即可。值得注意的是这里算的“重复出现次数”是允许重叠的。比如s aaaa长度为 3 的子串aaa出现了两次下标 0 和下标 1。如果题目要求“不重叠出现的次数”就不能直接用这个代码需要额外加“上一下标 L ≤ 当前下标”的判断这就复杂了属于进阶扩展。4.4 后缀数组思路简述如果面试官追问“有没有更好的解法”答案就是后缀数组。后缀数组的核心思想是把字符串的所有后缀按字典序排序排序后相邻的两个后缀的 LCP 一定是最长的候选。因为两个后缀如果前缀相同它们在字典序排序里就会靠得很近排序后相邻关系保证了不会漏掉任何一对潜在的最长公共前缀。定义sa[i]表示字典序第 i 小的后缀的起点下标height[i]表示第 i 名的后缀和第 i-1 名的后缀的最长公共前缀长度。那么整个字符串的最长重复子串长度就是height数组的最大值。这个结论非常干净。对于 n 到 10^5 级别用倍增法构造后缀数组是 O(n log n)用 DC3 可以做到 O(n)但常数很大。竞赛里通常 O(n log n) 的倍增法已经够用。缺点是代码长、细节多、容易写错优点是它不只是解决最长重复子串还能一次性解决很多高级字符串问题比如不同子串个数、最长回文子串等。我的建议是如果只是为了过题哈希二分的 O(n log n) 已经足够快代码量又少性价比最高如果是为了深入学习字符串算法后缀数组值得系统啃一遍它是很多高阶题的地基。简单验证用的教学版后缀数组可以直接用 Python 的切片排序实现def build_sa_simple(s: str): n len(s) sa sorted(range(n), keylambda i: s[i:]) rank [0] * n for idx, pos in enumerate(sa): rank[pos] idx height [0] * n k 0 for i in range(n): rk rank[i] if rk 0: k 0 continue j sa[rk - 1] while i k n and j k n and s[i k] s[j k]: k 1 height[rk] k if k: k - 1 return sa, height这个版本利用 Python 的切片的字典序比较代码很短但复杂度是 O(n^2 log n)只能用来验证小数据。在本地测试时拿它和上面的哈希二分结果对拍能有效确认算法正确性——对拍这个习惯强烈推荐比只看样例可靠得多。5. 实战复盘拼数(number)类变体怎么破回到开头提到的“拼数(number)”场景。小 r 拿到一个字符串 ss 由数字构成这类题的实际考察点经常是“先拼串再求最长连续相同段”。我把这个场景拆成两个具体的变体演示怎么把前面的模型套进去。5.1 变体一纯数字串里找最长连续相同段假设输入是一个数字字符串s 111223333求最长连续相同数字段长度。答案显然是4对应3333。这个变体完全等价于第 2 节的线性扫描只是字符集从任意字符变成了数字字符。代码照抄即可def longest_digit_run(s: str) - int: if not s: return 0 cur_len 1 best_len 1 for i in range(1, len(s)): if s[i] s[i - 1]: cur_len 1 else: cur_len 1 best_len max(best_len, cur_len) return best_len这里有一个小陷阱数字字符串里的字符1和整数1是不一样的。如果题目里有前导零的情况比如00100你一旦把字符串转成整数 100连续段信息就彻底丢失了。千万记住——题目说给字符串处理全程保持为字符串。5.2 变体二多段字符串拼接后跨边界最长段这是“拼数”里更有含金量的变体。给定若干段数字字符串按顺序拼接成一个大串求最终大串里的最长连续相同段长度。比如三段字符串分别有777、77和88拼接出来是7777788前两段交界处7连续了 5 次答案是 5。如果你直接对每一段分别求最长连续段然后取最大值会得到 3漏掉了跨边界的那一段。正确做法有两种。第一种最简单粗暴把所有段落真正拼起来然后整体扫描一遍。复杂度 O(总长度)完全够用。写起来也几乎没有思考成本def longest_after_join(parts: list[str]) - int: return longest_digit_run(.join(parts))第二种做法更有意思适合“不能真正拼成大串”的场景比如流式输入、内存受限或者要求边读边处理。核心思想是在扫描每一段时不仅要维护当前段内部的最长段还要知道“上一段尾部连续相同字符是什么长度是多少”。如果当前段开头的字符恰好和上一段尾部的字符相同那么跨边界连续段长度 上一段尾部连续长度 当前段头部连续长度用这个值去更新答案。def leading_len(seg: str) - int: cnt 0 ch None for c in seg: if c ch: cnt 1 else: ch c cnt 1 return cnt # 只在开头连续的情况下有效需要配合判断 def trailing_len(seg: str) - int: if not seg: return 0 cnt 1 for i in range(len(seg) - 2, -1, -1): if seg[i] seg[-1]: cnt 1 else: break return cnt def longest_cross_join(parts: list[str]) - int: best 0 prev_tail_char None prev_tail_len 0 for part in parts: if not part: continue # 当前段内部最长连续段 cur_best 1 cur_len 1 for i in range(1, len(part)): if part[i] part[i - 1]: cur_len 1 else: cur_len 1 cur_best max(cur_best, cur_len) best max(best, cur_best) # 跨边界合并 head_len leading_len(part) if set(part) {part[0]} or leading_len(part) 1 else 1 if prev_tail_char part[0]: cross_len prev_tail_len leading_len(part) best max(best, cross_len) # 更新上一段尾部信息 prev_tail_char part[-1] prev_tail_len trailing_len(part) return best这段代码里我故意写了leading_len的调用判断实际使用中直接使用leading_len(part)即可因为leading_len返回的永远是“从开头起连续相同的长度”等价于“头部连续长度”。trailing_len返回的则是“从结尾往前数连续相同的长度”。需要注意的一个边界如果上一段是777当前段是7xx跨边界长度是3 1 4这个判断是对的。但如果上一段是7单字符当前段是空串那要跳过因为空串没有开头字符。我在代码里用if not part: continue处理了。整体来看第二种做法在时间复杂度上仍然是 O(总长度)但节省了拼接大串的内存同时对输入是“流式逐段给出”的场景非常友好。5.3 完整解题流程面对这类变体题我建议按下面的步骤走先把所有输入理解清楚确认是“多个字符串拼接后统一处理”还是“每段独立处理”判断考察的是三种模型中的哪一种连续相同段、公共前缀、重复子串如果涉及拼接边界直接画几个边界例子比如777 77、123 34肉眼确认答案结构先写最笨的暴力版本生成随机小数据再写优化版本用暴力版对拍验证提交前把大数据极限跑一遍确认时间空间没有超限。这个流程说起来简单但在实际做题中帮我挡掉了至少一半的“自以为对了但 WA 到怀疑人生”的情况。字符串题尤其容易在边界条件上出问题对拍是性价比最高的调试手段。6. 藏在细节里的坑常见问题与排查技巧字符串处理的坑往往不在算法本身而在边边角角的小细节。我把这几年高频踩的坑整理成了一张速查表每一类问题都给出了具体的表现和解决办法。问题现象根本原因解决办法空串返回 0但单字符返回 1 没问题整体思路混乱没有先想清楚“连续相同串”的最小长度定义统一约定空串返回 0非空串至少返回 1二分 LCP 或重复子串长度时死循环mid的取法和lo/hi更新逻辑不配套使用mid (lo hi 1) // 2配合lo mid或使用while lo hi配合lo mid 1二选一不要混搭哈希取子串时负数报错或结果异常C 中取模结果是负数先加模数再取模Python 中无此问题哈希碰撞导致重复子串误判单模数哈希在数据量大时有碰撞可能碰撞后回查原字符串确认或直接用双哈希跨边界连续段答案偏小只对每段内部求最长段忽略了拼接点额外记录上一段尾部字符和尾部连续长度数字字符串被转成 int 后前导零丢失错误的类型转换始终坚持字符串处理输出子串时切片边界不对多一位或少一位左右闭开区间混淆统一用“左闭右开”[l, r)用s[l:l len]6.1 二分边界是重灾区二分模板的问题是字符串题当中出现率最高的低级错误。我见过很多次while lo hi和mid (lo hi) // 2配对上界更新hi mid的写法在求“最大满足条件的值”时会陷入死循环。比如lo 0, hi 1mid 0结果判定可行lo mid 0lo 不再变化死循环。我个人的习惯是写“答案记录法”while lo hi每次mid满足条件就更新答案变量并缩小下界不满足就缩小上界。这种写法直观也不容易写错唯一的代价是多花一行代码保存答案。6.2 哈希碰撞怎么压到最低如果你不想在哈希值相同时回查原字符串最稳的方案是双哈希。用两个不同的模数算两个哈希值只有两个哈希值都相等才认为子串相同。代码改动就是在build_hash里维护两组h和p在比较时同时比较两个值def build_double_hash(s: str): base 131 mod1 1_000_000_007 mod2 998_244_353 n len(s) h1 [0] * (n 1) h2 [0] * (n 1) p1 [1] * (n 1) p2 [1] * (n 1) for i, ch in enumerate(s): v ord(ch) p1[i 1] p1[i] * base % mod1 p2[i 1] p2[i] * base % mod2 h1[i 1] (h1[i] * base v) % mod1 h2[i 1] (h2[i] * base v) % mod2 return (h1, p1, mod1), (h2, p2, mod2) def get_double_hash(hp, l, r): (h1, p1, mod1), (h2, p2, mod2) hp val1 (h1[r] - h1[l] * p1[r - l]) % mod1 val2 (h2[r] - h2[l] * p2[r - l]) % mod2 return val1, val2双哈希在竞赛里的碰撞概率已经低到可以忽略不计配合不回查代码性能也更稳定。但如果是面试场合我仍然建议在口述时先讲清楚“哈希碰撞存在理论可能因此要保留字符串比对确认这一步”面试官很吃这一套因为它能体现出你对哈希本质的理解。6.3 复杂度实测对比与选型我拿几组典型规模的数据在本地跑过一遍量级大致如下Python 3普通笔记本字符串长度 n暴力枚举 O(n^3)线性扫描 O(n)哈希二分 O(n log n)100毫秒级微秒级毫秒级5×10^3秒级0.001 秒0.01 秒10^5不可用分钟级0.002 秒左右0.1 秒左右10^6不可用0.02 秒左右约 1 秒从表格可以看出线性扫描永远是性能王者只要题目问的是连续相同段就千万不要去搞哈希或后缀数组。哈希二分在 10^5 到 10^6 级别表现稳定是我处理“最长重复子串”类问题时最常用的方案。后缀数组的常数比哈希二分大实现也复杂但胜在能一次性派生很多高级结论适合作为长期储备。我的经验是先在草稿纸上判断清楚题目属于哪一种模型再去套模板。90% 的字符串处理题靠“线性扫描 哈希二分 双指针”这三板斧就能解决真正需要后缀数组的题目其实没有想象中那么多。把这三种工具的适用边界和实现细节都吃透比收集一百个模板管用得多。另外补一个小技巧本地写题时用random生成短字符串把暴力解和优化解的结果对拍跑几百组随机数据能覆盖绝大多数边界情况。这个习惯我保持了很长时间每次换新模板都会先对拍一遍再上 OJ基本上一交就过。字符串处理题不比其他类型刁钻只要边界守得住主流算法跑得快稳过是大概率的事。