企业官网建设流程全解析

做字符串处理的时候，最长相同字符串是我见过最容易被题目名称骗到的算法问题之一。我见过不少人一听到这五个字，立刻开写两重循环，然后在小数据上欢快地跑通，一换十万级测试集直接卡死。其实这个题目的难点不在“字符串”而在“相同”这两个字：你要求连续的相同片段，还是不连续的相同序列？是单个字符串内部找重复，还是两个字符串之间找公共部分？这两个问题看着像一道题，算法完全不同。

这篇文章不会给你堆一个“标准答案”，而是把这条路上我自己踩过的坑、反复验证过的方案、以及最后沉淀下来的一套判断逻辑讲清楚。无论你是准备面试、写数据清洗脚本，还是要处理大规模文本，都应该能从里面找到直接能抄的代码和一组值得放进个人工具箱的判断标准。

1. 先分清楚“最长相同字符串”到底指哪一道题

1.1 三个最容易被混在一起问的变体

我第一次刷到这类题目时，下意识以为是“两个字符串里最长的那段相同内容”。后来发现不对，题目原文写的是“最长相同字符串”，不一定是两个字符串之间的事情。网上常见的问法至少有三种：

其中第三类最容易让人误入歧途。因为很多文章把“Longest Common Subsequence”的缩写也写成 LCS，而“Longest Common Substring”的中文里也经常有人叫“最长公共子串”。这两个算法看起来很像，实际上完全不同：子串要求连续，子序列只要求顺序一致。

我自己碰到过现实版：帮人清洗一批地址数据时，需求是“找出两个地址里相同的最长片段”。一开始我按子序列做了，结果把“北京市海淀区中关村大街”和“北京市海淀区中关村南大街”匹配出了“北京市海淀区中关村大街”，后面的“南”字被跳过了。看起来匹配长度更长，但业务上完全不是想要的。地址这种格式化字段，必须找连续的公共片段，不是允许跳字的模糊匹配。

1.2 连续和非连续，算法完全是两套

连续子串有一个很好的性质：一旦中间某个字符不一致，匹配就断掉。这让“最长相同连续片段”可以用状态转移来刻画。

如果只在两个字符串 A 和 B 之间找最长公共子串，定义dp[i][j]为“以 A 的第 i 个字符、B 的第 j 个字符结尾的最长公共子串长度”，那么：

如果 A[i] == B[j]，dp[i][j] = dp[i-1][j-1] + 1 否则 dp[i][j] = 0

这个转移式的关键在else分支必须清零。很多人写到这里会把条件写反，或者忘了 else，导致匹配到中间断掉之后还在累计长度。清零的目的很简单：连续片段断了，以这个位置结尾的公共子串就不可能再延续下去，只能重新开始。

而非连续的子序列，转移式是：

如果 A[i] == B[j]，dp[i][j] = dp[i-1][j-1] + 1 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

同样是 LCS 简称，一个要清零，一个要取 max。面试里如果没先确认清楚，写反了能让你调试半小时。

1.3 题目没明说的两个边界：重叠与分隔符

单串内找“出现至少两次的最长片段”时，大家默认允许两个片段重叠。比如aaaa，允许重叠时最长重复片段是aaa，长度为 3；不允许重叠时最长只能取aa，长度为 2。很多题目没有明确写“允许重叠”，解法却默认允许。

另一个边界是分隔符。两个字符串拼接成一个字符串，用后缀数组求公共子串时，中间必须插入一个原串中不可能出现的字符。如果你没加分隔符，匹配结果可能横跨两个字符串，算出一个本来不属于任何单个字符串的“伪公共片段”。这个细节在 1.3 之后的小节里还会再遇到。

2. 暴力解法的推演过程：为什么字符串长到十万就会卡死

2.1 最直接的枚举写法

如果只是要求“先跑通”，最简单的做法是把一个字符串的所有子串都枚举出来，然后看另一个字符串里有没有。代码很短：

def brute_longest_common_substring(a, b): best = "" best_len = 0 for i in range(len(a)): for j in range(i + 1, len(a) + 1): sub = a[i:j] if sub in b and len(sub) > best_len: best = sub best_len = len(sub) return best

这个写法爽快，但复杂度很惊人。枚举所有子串本身就是 O(n²)，每个子串再执行一次字符串包含判断，Python 的in背后是 C 实现的快速匹配，最坏情况下仍然要 O(m) 甚至更多。整体最坏复杂度大概 O(n²·m)。两个 1000 字符的字符串，最坏要做上亿次比较，已经开始明显卡顿；两个 10000 字符的字符串，基本跑不出结果。

如果你要在单个字符串内部找最长重复片段，也可以写一个枚举版本：

def brute_longest_repeated_substring(s): n = len(s) best_len = 0 best_sub = "" for i in range(n): for j in range(i + 1, n + 1): length = j - i if length > best_len and s.find(s[i:j], i + 1) != -1: best_len = length best_sub = s[i:j] return best_sub

这里注意s.find(sub, i + 1)的作用：从当前起点后面再找一次，确认这个片段并非只出现一次。很多人会直接写sub in s，结果sub就是原字符串开头本身，永远为真，最后返回的必然是整个字符串。这个 bug 在单串问题时非常常见。

2.2 为什么 O(n³) 在小数据上“看不出问题”

暴力枚举的问题在于，数据量一上去，增长实在太快。假设单串长度 n 为 1000，枚举所有起点 1000 个、终点平均 500 个，大约有 50 万个子串，每个子串再查一次出现位置。即使每个子串 100 个字符，也是上亿次字符比较。这个量级在本地跑个几秒还能忍。

但 n 到 10000，子串数量接近 5000 万，再乘上子串长度，计算量到了几十亿次。如果算法题限制 1 秒到 2 秒，这已经不是“慢一点”的问题，是根本没有希望跑完。

很多初学者会用“我机器快”来安慰自己。实际上刷题网站里的评测机不会给你这种优待，真实生产环境里文本数据更是动不动几十万行。暴力枚举只能用来做两件事：验算小数据，以及给后续的优化算法当对照基准。

2.3 动态规划版本：空间换时间

从暴力枚举到动规，核心思路是避免重复比较。dp[i][j]把“以当前位置结尾的公共片段长度”存下来，不需要每次重新比较整个子串。

def lcs_substring_dp(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] best_len = 0 end_pos = -1 for i in range(1, n + 1): for j in range(1, m + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > best_len: best_len = dp[i][j] end_pos = i else: dp[i][j] = 0 if best_len == 0: return "" return a[end_pos - best_len:end_pos]

这个版本的时间复杂度是 O(n·m)，空间复杂度 O(n·m)。如果只求长度，可以把二维数组压成一维，因为每个dp[i][j]只依赖左上角的dp[i-1][j-1]，滚动数组完全够用。

动规适合两个串长度都在几千以内的场景。它逻辑简单，不容易写错，而且不需要处理哈希碰撞这类概率问题。一万乘一万就是一亿个状态，在 Python 里即使只存整数，也需要好几秒；十万乘十万的情况就不用想动规了。

2.4 DP 也不是万能的，长度十万就露馅

动规最大的问题是状态数受两个串长度乘积约束。单串内找最长重复子串也可以用动规，本质是“自己和自己的公共子串”，状态同样是 O(n²)。当 n 到十万量级，一亿以上的状态无论时间还是内存都无法接受。

我遇到过一份真实日志去重需求，单条记录平均 8 万个字符，要求找出每两条记录之间的最长公共片段。十分钟内如果把所有两两组合都做 O(n·m) 动态规划，哪怕 n 和 m 是两万对两万，也有 4 亿状态，光 Python 循环就要跑到天亮。

这类场景必须换思路：不再试图枚举所有起点，而是用“二分长度 + 哈希判定”的方式，把复杂度压到 O(n·log n) 附近。

3. 二分答案加滚动哈希：把“找最长”变成“是否存在”的工程派解法

3.1 核心思路：把求最长变成判定

二分答案的基础是单调性：如果一个字符串里存在长度为 L 的重复片段，那么长度为 L-1、L-2 的片段一定也存在，因为随便取那个重复片段的前缀就行。反过来，如果长度为 L 的片段不存在，那么更长的片段也不可能存在。

有了这个性质，就可以把“求最长”拆成 log n 次“判断长度 L 是否可行”。每次判断，只需要检查所有长度为 L 的子串有没有出现重复或交集。判断逻辑如果用哈希来做，复杂度可以从 O(n·m) 级别降到 O(n) 级别。

这个思路在工程上非常稳。你不需要写复杂的数据结构，只需要一个可靠的滑动窗口和一套哈希前缀表。

3.2 滚动哈希计算子串的数学原理

我们要能快速算出任意区间[l, r)子串的哈希值。做法是把字符串看成一个 base 进制的大数，然后用前缀哈希相减得到任意子串。

设h[i]表示前 i 个字符的哈希值，递推式：

h[i+1] = (h[i] * base + ord(s[i])) % mod

再预处理 base 的幂次数组pow[i]，那么子串s[l:r]的哈希值是：

(h[r] - h[l] * pow[r-l]) % mod

这套公式的原理和十进制数类似：12345去掉前两位变成345，用的就是12345 - 12 * 100。字符串哈希把每个字符当成一个“位”，子串哈希就是截取数字中连续的一段。

用 Python 实现如下：

MOD1 = 1_000_000_007 MOD2 = 1_000_000_009 BASE = 911382323 def build_hash(s): 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): code = ord(ch) h1[i + 1] = (h1[i] * BASE + code) % MOD1 h2[i + 1] = (h2[i] * BASE + code) % MOD2 p1[i + 1] = (p1[i] * BASE) % MOD1 p2[i + 1] = (p2[i] * BASE) % MOD2 return h1, h2, p1, p2 def sub_hash(h1, h2, p1, p2, l, r): length = r - l v1 = (h1[r] - h1[l] * p1[length]) % MOD1 v2 = (h2[r] - h2[l] * p2[length]) % MOD2 return v1, v2

注意下标：前缀数组长度为 n+1，h[i]对应前 i 个字符，所以闭区间统一写成[l, r)，避免+1/-1的混乱。

3.3 双哈希和碰撞风险

单模哈希在数据随机时碰撞概率很低，但绝对不是零。刷题平台如果允许 hacks，别人可以针对你的固定模数和 base 构造一堆碰撞数据；真实场景中，如果两条文本不同但哈希恰好相同，程序会给出错误结果。

双哈希的原理很简单：用两个不同的模数分别计算，两个值都相同才认为子串相同。碰撞概率从单个模数的约 1/mod 降到约 1/(mod1·mod2)，在正常数据规模下已经可以忽略。

如果你是做离线数据处理，不想引入任何随机性，也可以选择不依赖概率的方案，比如后缀数组。不过工程上双哈希的性价比非常高，代码只多了几行，运行时间也只多了不到一倍。

3.4 完整示例：单串最长重复子串

下面这段代码同时返回最长重复片段本身，而不是只返回长度。核心是二分长度，每次 check 时把所有长度为 mid 的子串哈希放进集合，再看有没有第二次出现。

def longest_repeated_substring(s): if not s: return "" n = len(s) h1, h2, p1, p2 = build_hash(s) def check(length): seen = set() for i in range(n - length + 1): key = sub_hash(h1, h2, p1, p2, i, i + length) if key in seen: return i, True seen.add(key) return -1, False left, right = 0, n - 1 best_start, best_len = 0, 0 while left <= right: mid = (left + right) // 2 start, ok = check(mid) if ok: best_start, best_len = start, mid left = mid + 1 else: right = mid - 1 return s[best_start:best_start + best_len] if best_len > 0 else ""

这个实现有一个边界要留意：check(0)恒为真，因为空串一定重复。所以best_len初始值应该为 0，最终判断best_len > 0再切片输出，否则可能返回一个奇怪的空切片。

二分次数是 log n，每次 check 要扫描整个字符串，所以整体时间复杂度 O(n·log n)。对十万级字符串，这个方案是可以接受的；百万级字符串，Python 里大概要跑几十秒，但已经比 O(n²) 的动规强了几个量级。

3.5 扩展到两个字符串的最长公共子串

如果题目是两个字符串之间找最长公共片段，二分思路同样成立：长度 L 可行，当且仅当 A 中存在一个长度为 L 的子串，同时它也出现在 B 中。

def longest_common_substring(a, b): if not a or not b: return "" n, m = len(a), len(b) ha1, ha2, pa1, pa2 = build_hash(a) hb1, hb2, pb1, pb2 = build_hash(b) def check(length): seen = set() for i in range(n - length + 1): seen.add(sub_hash(ha1, ha2, pa1, pa2, i, i + length)) for j in range(m - length + 1): if sub_hash(hb1, hb2, pb1, pb2, j, j + length) in seen: return j, True return -1, False left, right = 0, min(n, m) best_start, best_len = 0, 0 while left <= right: mid = (left + right) // 2 start, ok = check(mid) if ok: best_start, best_len = start, mid left = mid + 1 else: right = mid - 1 return b[best_start:best_start + best_len] if best_len > 0 else ""

代码里返回的是 B 中的片段，所以用best_start记录 B 中的起点。这个版本的空间主要花在seen集合上，最坏情况下集合里会存 n 个哈希对，内存占用还是可控的。

如果两个字符串很长，我更建议先判断max(len(a), len(b))再决定走哈希还是走后缀数组。一般经验是：长度在一万以内，动规最容易写；长度到十万，二分哈希最稳；长度到百万，后缀数组或后缀自动机才是更合适的解法。

4. 后缀数组与 height 数组：教科书里常见但工程上要取舍的思路

4.1 后缀数组是什么

后缀数组把字符串的所有后缀按字典序排成一个数组。比如字符串banana，所有后缀是：

banana anana nana ana na a

按字典序排序后，相邻两个后缀之间的公共前缀长度（LCP）保存在 height 数组里。这个结构非常优雅，因为它把“所有片段重复情况”压缩成了“相邻后缀的比较结果”。

人类很难直接看排序后的后缀找出答案，但计算机可以。一个最简单的、只能用于理解的后缀数组构建方式是：

def naive_sa(s): return sorted(range(len(s)), key=lambda i: s[i:])

这个写法在 n 很小时没问题。但千万别用在真实数据上：对 10 万个后缀做排序，每次比较都要比较两个字符串切片，最坏情况下一次比较就是 O(n)，整体复杂度接近 O(n²·log n)，跑一次足以让你怀疑人生。

4.2 最长重复子串 = 相邻后缀的最大 LCP

为什么最长重复子串等于 height 数组的最大值？原理是：任意两个后缀如果存在公共前缀，那么它们的公共部分必然出现在原串中至少两次。在后缀按字典序排序后，拥有最长公共前缀的两个后缀一定排在一起。这不是巧合，而是字典序的性质——相似的后缀会被排到相邻位置。

求 height 数组的标准写法是 Kasai 算法。它利用一个关键性质：height[rank[i]] >= height[rank[i-1]] - 1，从而把总复杂度压到 O(n)。

def build_height(s, sa): n = len(s) rank = [0] * n for i, pos in enumerate(sa): rank[pos] = i height = [0] * n k = 0 for i in range(n): if rank[i] == 0: k = 0 continue j = sa[rank[i] - 1] while i + k < n and j + k < n and s[i + k] == s[j + k]: k += 1 height[rank[i]] = k if k: k -= 1 return height

得到 height 数组之后，单串最长重复子串的长度就是max(height)。想要具体内容，找到那个最大值对应的后缀，再截取前面长度相同的部分即可。

4.3 两个字符串时用分隔符拼接

两个字符串之间找最长公共子串，经典的套路是拼接：s = A + "\0" + B。分隔符必须保证原始字符串里不可能出现。然后求拼接串的后缀数组和 height 数组，答案就是“相邻两个后缀分别来自 A 和 B 时”的 height 最大值。

s = a + "\0" + b sa = build_sa(s) # 商用/竞赛版后缀数组构建 height = build_height(s, sa) def belong(pos): return 0 if pos < len(a) else 1 ans = 0 for i in range(1, len(s)): if belong(sa[i - 1]) != belong(sa[i]): ans = max(ans, height[i])

这个方案逻辑很干净，而且不依赖哈希碰撞概率。但实现起来需要一份可靠的后缀数组构建代码，倍增法、SA-IS 都不短。如果你只是临时算一次，二分哈希反而更省事。

4.4 工程落地时的取舍

我自己的习惯是：如果是竞赛或在线评测，哈希二分是最常用武器，因为代码短、调试快、可迁移性强；如果是离线工具，数据量大到百万级别，或者不允许任何碰撞概率，我才会把后缀数组的库拉进来。

后缀数组也不是银弹。它在 Python 里最麻烦的地方是构建部分没有内置实现，自己写倍增法容易因为常数太大而跑得比哈希还慢。必要的时候可以考虑调用pydivsufsort这类基于 C 实现的库，而不是硬写一套纯 Python 后缀数组。

后缀自动机理论上能做到 O(n)，但理解门槛更高，写起来也更容易出错。在没有明确性能瓶颈之前，我不会一上来就上后缀自动机。

5. 中文场景、字符编码和其他容易被忽略的细节

5.1 按字符还是按字节计算

初学算法时，大家处理的都是英文字母，一个字符对应一个字节，问题不大。但中文场景下，字符串处理这四个字在 UTF-8 编码里占 12 个字节，在 GBK 里占 8 个字节，在 Python 字符串对象里则是 4 个 Unicode 码点。

算法题里说“字符串长度”，通常指字符个数，不是字节数。但真实文件处理时，你经常拿到的是 bytes。如果在 bytes 层面找最长相同片段，有可能在一个中文字符的内部字节中截断，生成既不是合法字符也不是用户预期内容的“半截字符”。

我在一次清洗文案数据时，就遇到过两个文本在字节层面能匹配出一段奇怪的东西：其中一个文本是 UTF-8 编码，另一个被错误地按 GBK 解码后再编码，结果两边的字节流完全不同，任何字符串匹配算法都找不到业务意义上的公共片段。最后先统一编码格式，再做匹配，结果立刻正常了。

5.2 Python 的内存和 for 循环代价

双哈希的 build 过程需要四个长度为 n 的数组。如果字符长度是 100 万，每个 Python int 在列表里大约占 28 到 32 字节，四个数组动辄上百 MB。这种情况下内存可能比时间更先爆掉。

如果你只是求长度，不要求输出具体片段，可以把前缀数组改成滚动更新的方式。但二分哈希需要任意区间查询，前缀数组没法省；只能考虑换后缀数组、后缀自动机，或者把数据切成小块处理。

另外，for i, ch in enumerate(s)遍历的不是字节而是 Unicode 字符。对于纯 ASCII 日志，可以先将字符串编码成 bytes，再按字节遍历，速度通常会更快一点，但要注意边界问题：一旦出现中文字符，字节遍历就不要再用了。

5.3 现实数据里的乱码与归一化

真实文本里还有个很经典的坑：同一个字可能有不同编码形式。比如é可以由一个 Unicode 码点表示，也可以由e加组合用音符号的两个码点拼成。视觉上完全一样，字符串比较却不同。处理前调用unicodedata.normalize做归一化，是个好习惯。

空格、全角/半角、大小写也是隐藏的雷。很多所谓“相同字符串”的需求，其实业务上希望忽略大小写和空格。如果算法层面不做预处理，后面所有优化都是白搭。我的做法是先明确一套清洗规则：是否忽略大小写、是否压缩连续空格、是否保留中文标点。把规则固定下来，再进入匹配阶段。

6. 我自己在真实项目里踩过的坑和一套可复用的验证方法

6.1 一次单模哈希碰撞的教训

有次写一个文本查重工具，为了图快，只用了单模数1_000_000_007，base 选了常见的 131。随机小样本对拍都通过了，但跑一批真实日志时，程序返回了一个明显不合理的长片段。我起初怀疑是前缀哈希的边界公式写错，手工验证了十来个位置，公式没问题。

后来用暴力算法对同一组数据比，才发现问题出在碰撞。两个完全不同的子串在模1e9+7下哈希值相同，集合判断误认为它出现了两次。这次之后我再也没有用单模哈希处理重要数据。双模哈希多花的几十毫秒，和出错后排查的几小时相比，根本不值一提。

6.2 边界用例清单

任何字符串匹配算法上线前，我都会跑下面这组用例：

这些用例看起来简单，却能精准卡掉大部分错误实现。我自己至少两次因为漏掉“一个串是另一个串的前缀”这种情况，导致输出结果只剩半个公共片段。

6.3 随机对拍脚本，防止改一个长度就坏一个地方

优化算法时最怕“小数据过了，大数据挂了”。我习惯写一个随机对拍脚本，把暴力枚举和小规模随机字符串当作裁判，验证复杂算法输出是否一致。以下是一个针对单串最长重复子串的对拍样例：

import random def brute_repeated(s): n = len(s) best = "" for i in range(n): for j in range(i + 1, n + 1): sub = s[i:j] if s.find(sub, i + 1) != -1 and len(sub) > len(best): best = sub return best def optimized(s): return longest_repeated_substring(s) random.seed(2024) for _ in range(5000): n = random.randint(1, 40) s = "".join(random.choice("abc") for _ in range(n)) if brute_repeated(s) != optimized(s): print("mismatch:", s) break else: print("all ok")

用三个字符的小字母表生成随机串，既能让暴力算法快速跑完，又能覆盖大量重复结构。如果对拍通过，你对哈希公式边界的信心会高很多。换不同字母表、不同字符串长度、不同随机种子再跑几轮，基本能排除实现层面的低级错误。

6.4 工程中到底要不要自己写

如果是生产系统，我建议先看看手头数据规模再决定。几 KB 级别的文本，直接用动态规划或者 Pythondifflib.SequenceMatcher都行；几十 MB 级别的文本，不要自己造轮子，找一个维护良好的 C 扩展库更明智；只有在大规模且私有化部署不方便引入第三方依赖时，才值得把二分哈希或后缀数组手写完整。

个人项目里，二分哈希已经能覆盖九成需求。后缀数组更适合那些需要反复查询、数据量极大、且不能接受碰撞的场景。而动态规划永远是个不错的兜底方案，尤其当字符串长度不超过几千时，它的简单性本身就是最大优点。

最后再分享一个小技巧：别把“最长”两个字理解成一定要一次算出来。很多场景其实只需要一个阈值判断，比如“是否存在长度超过 20 的相同片段”。这种情况下，把二分答案改成直接判断固定长度，代码会简单很多，速度也快很多。先和业务方确认“多长才算足够长”，往往比闷头追求全局最优解更实际。