- 正确答案：最长公共子串（Longest Common Substring）是指在两个字符串中连续出现的最长相同子串。例如，字符串 "abcdxyz" 和 "xyzabcd" 的最长公共子串是 "abcd" 或 "xyz"（长度为4）。解决该问题的经典方法是使用动态规划。示例输入： str1 = "abcdxyz" str2 = "xyzabcd" 输出：4（最长公共子串的长度） - 解答思路： 1. 定义状态：设 dp[i][j] 表示以 str1 的第 i 个字符和 str2 的第 j 个字符结尾的公共子串的长度。 2. 状态转移方程： - 如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1 - 否则 dp[i][j] = 0（因为子串必须连续，一旦不匹配就断开） 3. 初始化：dp[0][j] = 0，dp[i][0] = 0（空字符串与任何字符串的公共子串长度为0） 4. 在填充 dp 表的过程中记录最大值及其位置，以便最后可以回溯出具体的子串。时间复杂度：O(m * n)，空间复杂度：O(m * n)，其中 m 和 n 分别是两个字符串的长度。 - 深度知识讲解：最长公共子串与最长公共子序列（LCS）不同，关键在于“连续性”。子序列不要求连续，而子串必须是原字符串中连续的一段。动态规划表的设计体现了对“状态”的精确建模。此处的状态定义非常关键：dp[i][j] 不表示前 i 和前 j 个字符的最长公共子串长度，而是“以 str1[i-1] 和 str2[j-1] 结尾”的公共子串长度。这种定义方式使得我们能利用前一个状态进行递推。底层数据结构是一个二维数组，用于存储中间结果。由于每个状态只依赖于左上角的值，理论上可以优化空间到 O(min(m, n))，甚至用滚动数组优化到 O(n)。但为了清晰表达逻辑，通常保留完整二维数组。进一步扩展： - 可以通过记录 maxLen 和结束位置来重构实际的子串。 - 若题目要求输出所有最长公共子串，可在遍历过程中将所有达到最大长度的子串起始位置记录下来。 - 使用后缀数组或后缀自动机可以在 O(n + m) 时间内解决，适用于大规模文本匹配，但在面试中较少要求实现。注意边界处理：当任意一个字符串为空时，结果为0。 - 代码示例（C++ 风格伪代码）： ``` #include #include #include using namespace std; string longestCommonSubstring(string str1, string str2) { int m = str1.length(); int n = str2.length(); // 创建 dp 表，大小为 (m+1) x (n+1) vector> dp(m + 1, vector(n + 1, 0)); int maxLength = 0; int endingPosInStr1 = 0; // 记录最长子串在 str1 中的结束位置 // 填充 dp 表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; if (dp[i][j] > maxLength) { maxLength = dp[i][j]; endingPosInStr1 = i; } } else { dp[i][j] = 0; } } } // 提取最长公共子串 if (maxLength == 0) { return ""; } return str1.substr(endingPosInStr1 - maxLength, maxLength); } // 测试函数 int main() { string str1 = "abcdxyz"; string str2 = "xyzabcd"; cout << "最长公共子串: " << longestCommonSubstring(str1, str2) << endl; return 0; } ``` - 关键点总结： 1. 状态定义必须强调“以当前字符结尾”，这是保证连续性的核心。 2. 匹配失败时清零，体现子串的连续特性。 3. 维护全局最大值变量来跟踪最终结果。 4. 可通过起始索引还原原始子串内容。 - 常见变种题型： - 返回所有最长公共子串（可能有多个） - 找三个或更多字符串的最长公共子串 - 允许最多 k 个字符不同的最长近似公共子串（可用滑动窗口或动态规划扩展）掌握此题有助于理解动态规划中状态设计的重要性，尤其是如何通过状态语义控制解的性质（如连续性）。

字节大模型-风控面经

全站热榜

创作者周榜