P3440. 寻找重复代码

解题思路

注意：本题和 最长重复子数组 几乎完全一致。唯一区别在于，本题要计算的不是最长公共子串的长度，而是要输出最长公共子串本身。

这是一个典型的 dp 问题。我们考虑动态规划三部曲：

dp 数组的含义是什么？

dp 数组是一个大小为 (N+1) * (M+1) 的二维矩阵，dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的 公共的、长度最长的连续子串的长度。

动态转移方程是什么？

如果发现 text1 的当前元素（即位置为 i-1 的元素）与 text2 的当前元素（即位置为 j-1 的元素）相同。此时，找到了一个公共元素，公共的、长度最长的子串的长度加 1。

dp 数组如何初始化？

dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度，此时该长度为 0。 text1 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0。

考虑完上述问题后，代码其实 呼之欲出。

复杂度分析 设 m 为 text1 的长度，n 为 text2 的长度，题面约束两者均不超过 100。

• 时间复杂度：O(m × n)。主体是双重循环填一张 (m+1) × (n+1) 的表，每个格子只做一次字符比较；只有当最长长度 maxLength 被刷新时才截取一次子串，刷新至多发生 min(m, n) 次，每次截取的代价不超过 min(m, n)，在本题 100 以内的规模下可以忽略，整体仍由双重循环主导。
• 空间复杂度：O(m × n)，用于整张二维 dp 表；另有答案字符串至多 min(m, n) 个字符。

补充说明：dp[i][j] 只依赖左上方的 dp[i-1][j-1]，若只需要最长公共子串的长度，可以用滚动数组把空间优化到 O(min(m, n))；但本题要输出子串本身，保留结束位置信息（代码通过 i 和 maxLength 反推起点）更直接。