题目描述与示例
题目
小明负责维护项目下的代码，需要查找出重复代码，用以支撑后续的代码优化，请你帮助小明找出重复的代码。 重复代码查找方法：以字符串形式给出两行代码text1，text2（字符串长度1 < len(text1)，len(text2) <= 100，由英文字母、数字和空格组成），找出两行代码中的最长公共子串。如果不存在公共子串，返回空字符串。
注意子串是连续的。
题目练习网址：https://www.algomooc.com/problem/P3440
输入
输入的参数text1，text2分别表示两行代码
输出
输出任一最长公共子串。
示例一
输入
hello123world hello123abc4 输出
hello123 示例二
输入
private_void_method public_void_method 输出
_void_method 示例三
输入
hiworld hiweb 输出
hiw 解题思路
注意：本题和LC718. 最长重复子数组几乎完全一致。唯一区别在于，本题要计算的不是最长公共子串的长度，而是要输出最长公共子串本身。
这是一个典型的dp问题。我们考虑动态规划三部曲：
dp数组的含义是什么？
dp数组是一个大小为(N+1)*(M+1)的二维矩阵，dp[i][j]表示text1前i个元素和text2前j个元素的公共的、长度最长的连续子串的长度。
- 动态转移方程是什么？
- 如果发现
text1的当前元素，即位置为i-1的元素，与text2的当前元素即位置为j-1的元素相同。此时，找到了一个公共元素，公共的、长度最长的子串的长度加1。
if text1[i-1] == text2[j-1]: dp[i][j] = dp[i - 1][j - 1] + 1 dp数组如何初始化？
dp[0][0]表示text1前0个元素和text2前0个元素的公共的、长度最长的子串的长度，此时公共的、长度最长的子串的长度为0。text1或者text2没有字符时，公共的、长度最长的子串的长度都为0。
dp = [[0] * (n + 1) for _ in range(m + 1)] dp[0][0] = 0 for i in range(1, m+1): dp[i][0] = 0 for j in range(1, n+1): dp[0][j] = 0 考虑完上述问题后，代码其实呼之欲出了。
代码
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！ # 地址：https://www.odalgo.com text1 = input() text2 = input() # 获取 text1 的长度 m = len(text1) # 获取 text2 的长度 n = len(text2) # 设置数组 dp，用来存储 text1 和 text2 公共的、长度最长的子串的长度 # dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度 # dp[2][3] 表示 text1 前 2 个元素和 text2 前 3 个元素的公共的、长度最长的子串的长度 # dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度 # 前 i 个元素的区间为 [0, i-1] # dp[m][n] 表示 text1 前 m 个元素和 text2 前 n 个元素的公共的、长度最长的子串的长度 # 前 m 个元素的表示区间为 [0, m]，前 n 个元素的表示区间为 [0, n] # 因此，dp 数组的长度为 m + 1 和 n + 1 dp = [[0] * (n + 1) for _ in range(m + 1)] # maxLength 表示 dp 数组中的最大值 maxLength = 0 # 初始化答案变量为空串 ans = "" # 1. 初始化dp数组 # dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度 # text1 text2 也没有元素 # 因此，公共的、长度最长的子串的长度为 0 dp[0][0] = 0 # text1 没有元素 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0 for i in range(1, m+1): dp[i][0] = 0 for j in range(1, n+1): dp[0][j] = 0 # i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个元素 for i in range(1, m+1): # j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个元素 for j in range(1, n+1): # 2. 动态转移方程 # 如果发现 text1 的当前元素，即位置为 i - 1 的元素 # 与 text2 的当前元素，即位置为 j - 1 的元素【相同】 # 此时，找到了一个公共元素，公共的、长度最长的子串的长度加 1 if text1[i - 1] == text2[j - 1]: # dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度 # dp[i - 1][j - 1] 表示 text1 前 i - 1 个元素和 text2 前 j - 1 个元素的公共的、长度最长的子串的长度 dp[i][j] = dp[i - 1][j - 1] + 1 # 更新最长的子串的长度 if maxLength < dp[i][j]: maxLength = dp[i][j] # 最长子串长度为maxLength，对于text1而言， # 当前结束位置为i，当前开始位置为i-maxLength # 这里换成text2[j-maxLength: j]也是一样的 ans = text1[i-maxLength: i] # 返回结果 print(ans) Java
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String text1 = scanner.nextLine(); String text2 = scanner.nextLine(); int m = text1.length(); int n = text2.length(); int[][] dp = new int[m + 1][n + 1]; int maxLength = 0; String ans = ""; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; if (maxLength < dp[i][j]) { maxLength = dp[i][j]; ans = text1.substring(i - maxLength, i); } } } } System.out.println(ans); } } C++
#include <iostream> #include <string> #include <vector> using namespace std; int main() { string text1, text2; getline(cin, text1); getline(cin, text2); // 获取 text1 的长度 int m = text1.length(); // 获取 text2 的长度 int n = text2.length(); // 设置数组 dp，用来存储 text1 和 text2 公共的、长度最长的子串的长度 // dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度 // dp[2][3] 表示 text1 前 2 个元素和 text2 前 3 个元素的公共的、长度最长的子串的长度 // dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度 // 前 i 个元素的区间为 [0, i-1] // dp[m][n] 表示 text1 前 m 个元素和 text2 前 n 个元素的公共的、长度最长的子串的长度 // 前 m 个元素的表示区间为 [0, m]，前 n 个元素的表示区间为 [0, n] // 因此，dp 数组的长度为 m + 1 和 n + 1 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // maxLength 表示 dp 数组中的最大值 int maxLength = 0; // 初始化答案变量为空串 string ans = ""; // 1. 初始化dp数组 // dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度 // text1 text2 也没有元素 // 因此，公共的、长度最长的子串的长度为 0 dp[0][0] = 0; // text1 没有元素 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0 for (int i = 1; i <= m; ++i) { dp[i][0] = 0; } for (int j = 1; j <= n; ++j) { dp[0][j] = 0; } // i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个元素 for (int i = 1; i <= m; ++i) { // j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个元素 for (int j = 1; j <= n; ++j) { // 2. 动态转移方程 // 如果发现 text1 的当前元素，即位置为 i - 1 的元素 // 与 text2 的当前元素，即位置为 j - 1 的元素【相同】 // 此时，找到了一个公共元素，公共的、长度最长的子串的长度加 1 if (text1[i - 1] == text2[j - 1]) { // dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度 // dp[i - 1][j - 1] 表示 text1 前 i - 1 个元素和 text2 前 j - 1 个元素的公共的、长度最长的子串的长度 dp[i][j] = dp[i - 1][j - 1] + 1; // 更新最长的子串的长度 if (maxLength < dp[i][j]) { maxLength = dp[i][j]; // 最长子串长度为maxLength，对于text1而言， // 当前结束位置为i，当前开始位置为i-maxLength // 这里换成text2[j-maxLength: j]也是一样的 ans = text1.substr(i - maxLength, maxLength); } } } } // 返回结果 cout << ans << endl; return 0; } C
#include <stdio.h> #include <string.h> #include <stdlib.h> char* findLongestCommonSubstring(char* text1, char* text2) { int m = strlen(text1); int n = strlen(text2); // 动态分配 dp 数组 int** dp = (int**)malloc((m + 1) * sizeof(int*)); for (int i = 0; i <= m; i++) { dp[i] = (int*)calloc(n + 1, sizeof(int)); } int maxLength = 0; // 记录最长公共子串的长度 int endIndex = 0; // 记录最长子串在 text1 中的结束索引 // 遍历 text1 和 text2 的所有字符 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLength) { maxLength = dp[i][j]; endIndex = i; } } } } // 提取最长公共子串 char* ans = (char*)malloc((maxLength + 1) * sizeof(char)); strncpy(ans, text1 + endIndex - maxLength, maxLength); ans[maxLength] = ' '; // 释放动态分配的内存 for (int i = 0; i <= m; i++) { free(dp[i]); } free(dp); return ans; } int main() { char text1[1001], text2[1001]; scanf("%s %s", text1, text2); char* result = findLongestCommonSubstring(text1, text2); printf("%sn", result); free(result); // 释放返回字符串的内存 return 0; } Node JavaScript
function findLongestCommonSubstring(text1, text2) { const m = text1.length; const n = text2.length; // 初始化 dp 数组 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); let maxLength = 0; // 记录最长公共子串的长度 let endIndex = 0; // 记录最长子串在 text1 中的结束索引 // 遍历 text1 和 text2 的所有字符 for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (text1[i - 1] === text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLength) { maxLength = dp[i][j]; endIndex = i; } } } } // 提取最长公共子串 return text1.slice(endIndex - maxLength, endIndex); } // 测试主函数 const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); rl.question('', (line1) => { rl.question('', (line2) => { console.log(findLongestCommonSubstring(line1, line2)); rl.close(); }); }); Go
package main import ( "bufio" "fmt" "os" ) func findLongestCommonSubstring(text1, text2 string) string { m, n := len(text1), len(text2) // 初始化 dp 数组 dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, n+1) } maxLength := 0 // 记录最长公共子串的长度 endIndex := 0 // 记录最长子串在 text1 中的结束索引 // 遍历 text1 和 text2 的所有字符 for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if text1[i-1] == text2[j-1] { dp[i][j] = dp[i-1][j-1] + 1 if dp[i][j] > maxLength { maxLength = dp[i][j] endIndex = i } } } } // 提取最长公共子串 return text1[endIndex-maxLength : endIndex] } func main() { reader := bufio.NewReader(os.Stdin) text1, _ := reader.ReadString('n') text2, _ := reader.ReadString('n') // 去掉末尾的换行符 text1 = text1[:len(text1)-1] text2 = text2[:len(text2)-1] result := findLongestCommonSubstring(text1, text2) fmt.Println(result) } 时空复杂度
时间复杂度：O(MN)。dp过程需要经历双重循环。
空间复杂度：O(MN)。二维dp数组所占据的空间。
M、N分别为text1、text2的长度。
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/3.jpg&w=218&h=124&zc=1)
