华为od机考2025A卷真题 -寻找重复代码

6bOZWv

题目描述与示例

题目

小明负责维护项目下的代码，需要查找出重复代码，用以支撑后续的代码优化，请你帮助小明找出重复的代码。 重复代码查找方法：以字符串形式给出两行代码text1，text2（字符串长度1 < len(text1)，len(text2) <= 100，由英文字母、数字和空格组成），找出两行代码中的最长公共子串。如果不存在公共子串，返回空字符串。
注意子串是连续的。
题目练习网址：https://www.algomooc.com/problem/P3440
输入

输入的参数text1，text2分别表示两行代码
输出

输出任一最长公共子串。
示例一

输入

hello123worldhello123abc4输出

hello123示例二

输入

private_void_methodpublic_void_method输出

_void_method示例三

输入

hiworldhiweb输出

hiw解题思路

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

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

• dp数组的含义是什么？
  

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

• 动态转移方程是什么？
  

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

if text1[i-1] == text2[j-1]:    dp[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] = 0for i in range(1, m+1):    dp[0] = 0for j in range(1, n+1):    dp[0][j] = 0考虑完上述问题后，代码其实呼之欲出了。
代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！# 地址：https://www.odalgo.comtext1 = 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[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 + 1dp = [[0] * (n + 1) for _ in range(m + 1)]# maxLength 表示 dp 数组中的最大值maxLength = 0# 初始化答案变量为空串ans = ""# 1. 初始化dp数组# dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度# text1 text2 也没有元素# 因此，公共的、长度最长的子串的长度为 0dp[0][0] = 0# text1 没有元素 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0for i in range(1, m+1):    dp[0] = 0for 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[j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度            # dp[i - 1][j - 1] 表示 text1 前 i - 1 个元素和 text2 前 j - 1 个元素的公共的、长度最长的子串的长度            dp[j] = dp[i - 1][j - 1] + 1            # 更新最长的子串的长度            if maxLength < dp[j]:                maxLength = dp[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[j] = dp[i - 1][j - 1] + 1;                    if (maxLength < dp[j]) {                        maxLength = dp[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[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[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[j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度                // dp[i - 1][j - 1] 表示 text1 前 i - 1 个元素和 text2 前 j - 1 个元素的公共的、长度最长的子串的长度                dp[j] = dp[i - 1][j - 1] + 1;                // 更新最长的子串的长度                if (maxLength < dp[j]) {                    maxLength = dp[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 = (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[j] = dp[i - 1][j - 1] + 1;                if (dp[j] > maxLength) {                    maxLength = dp[j];                    endIndex = i;                }            }        }    }    // 提取最长公共子串    char* ans = (char*)malloc((maxLength + 1) * sizeof(char));    strncpy(ans, text1 + endIndex - maxLength, maxLength);    ans[maxLength] = '\0';    // 释放动态分配的内存    for (int i = 0; i <= m; i++) {        free(dp);    }    free(dp);    return ans;}int main() {    char text1[1001], text2[1001];    scanf("%s %s", text1, text2);    char* result = findLongestCommonSubstring(text1, text2);    printf("%s\n", 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[j] = dp[i - 1][j - 1] + 1;                if (dp[j] > maxLength) {                    maxLength = dp[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 mainimport (        "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 = 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[j] = dp[i-1][j-1] + 1                                if dp[j] > maxLength {                                        maxLength = dp[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的长度。