C++如何计算两个字符串的最大公共子串长度-C++-PHP中文网

最长公共子串长度可用二维dp求解：dpi表示以s1[i-1]和s2[j-1]结尾的公共子串长度，相等时dpi=dpi-1+1，否则为0，过程中更新最大值。

c++如何计算两个字符串的最大公共子串长度

用动态规划求解 `lcs_length` 最直观

最大公共子串（注意不是子序列）要求字符连续、位置对应。最稳的解法是二维 DP：设 dp[i][j] 表示以 s1[i-1] 和 s2[j-1] 结尾的公共子串长度。状态转移很简单：
– 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
– 否则 dp[i][j] = 0。
过程中记录最大值即可。

关键点在于：子串必须连续，所以不匹配时必须清零，这点和最长公共子序列（LCS）完全不同。

空间可优化到 O(min(m,n))，只保留上一行
初始化全为 0，无需特殊边界处理
别把 dp 数组开成 [m+1][n+1] 却索引越界——常见错误是循环写成 i 但访问 <code>s1[i]

用滚动数组节省内存时注意索引偏移

当字符串很长（比如几万字符），二维数组可能爆内存。改用一维 dp[j] 滚动更新，需从后往前遍历 j，否则会覆盖上一轮值。核心逻辑：

int prev = 0; // 相当于 dp[i-1][j-1]
for (int j = 1; j 
<p>这个写法比单纯倒序更安全，避免因覆盖导致错误递推。</p>

每次外层循环开始前要重置 prev = 0
dp 数组长度为 n+1，下标 0 不参与计算（保持为 0）
如果只要长度不要子串内容，这个版本足够；若需返回具体子串，得额外记录结束位置

遇到空字符串或单字符要快速返回

边界情况不是点缀，而是高频出错点。比如 s1 = "" 或 s2 = "a"，直接返回 0，不必进 DP 循环。实操中建议前置校验：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

任一字符串为空 → 返回 0
任一字符串长度为 1 → 可直接用 find() 判断是否存在该字符，省去建数组开销
两个字符串完全相等 → 直接返回其长度，避免无谓计算

这些判断花不了几个 CPU 周期，却能拦住不少线上 case 的异常分支。

别混淆“子串”和“子序列”，错误常出现在题目理解阶段

面试或 OJ 题里，“最长公共子串”（Longest Common Substring）和“最长公共子序列”（LCS）名字太像，但解法和复杂度差很多。前者要求连续，时间复杂度 O(mn)，空间可压；后者不要求连续，DP 状态不变但转移时不清零，且无法空间压缩到一维。

典型错误现象：
– 输出结果比预期大（误用了 LCS 的转移逻辑）
– 对于 "abc" 和 "acb" 返回 2（实际应为 1，因为只有 "a" 或 "b" 或 "c" 是公共子串）
– 提交后部分 case 通过，但长字符串超时（用了暴力 O(mn*min(m,n)) 枚举）

真正难的不是写对代码，而是读题时盯住“子串”两个字，确认是否允许跳字符。