当前位置：首页 > news >正文

华为OD机试 - 查找重复代码 - 动态规划（Python/JS/C/C++ 2025 A卷 100分）

news 2025/3/18 5:23:39

在这里插入图片描述

2025华为OD机试题库（按算法分类）：2025华为OD统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

小明负责维护项目中的代码，需要查找出重复代码，用以支撑后续的代码优化，请你帮助小明找出重复的代码。

重复代码查找方法：

以字符串形式给定两行代码，找出两行代码中的最长公共子串。

如果不存在公共子串，返回空。

二、输入描述

输入两行代码。

三、输出描述

输出最长公共子串。

四、Python算法源码

# Python代码：使用动态规划寻找最长公共子串def longest_common_substring(a: str, b: str) -> str:m, n = len(a), len(b)# 创建二维列表dp，大小为(m+1) x (n+1)，所有元素初始化为0dp = [[0] * (n + 1) for _ in range(m + 1)]max_len = 0      # 记录最长公共子串的长度end_index = 0    # 记录在字符串a中最长公共子串的结束位置# 遍历字符串a和b的每个字符for i in range(1, m + 1):for j in range(1, n + 1):if a[i - 1] == b[j - 1]:# 如果字符相同，则当前dp值等于左上角dp值加1dp[i][j] = dp[i - 1][j - 1] + 1if dp[i][j] > max_len:max_len = dp[i][j]end_index = i  # 更新最长公共子串在a中的结束位置# 返回最长公共子串，如果max_len为0，则返回空字符串return a[end_index - max_len:end_index]if __name__ == "__main__":# 读取两行输入，使用strip()去掉末尾换行符a = input().strip()b = input().strip()# 输出最长公共子串print(longest_common_substring(a, b))

五、JavaScript算法源码

/*
JavaScript代码：使用动态规划寻找最长公共子串
*/// 定义函数，接收两个字符串参数
function longestCommonSubstring(a, b) {let m = a.length, n = b.length;// 创建二维数组dp，大小为(m+1) x (n+1)，所有元素初始化为0let dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));let maxLen = 0;   // 记录最长公共子串的长度let endIndex = 0; // 记录最长公共子串在字符串a中的结束位置// 遍历字符串a和bfor (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {if (a[i - 1] === b[j - 1]) {// 如果字符相同，则dp[i][j]等于左上角dp值加1dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > maxLen) {maxLen = dp[i][j];endIndex = i; // 更新最长公共子串的结束位置}}}}// 返回最长公共子串，如果maxLen为0，则返回空字符串return a.substring(endIndex - maxLen, endIndex);
}// 以下为测试代码，使用Node.js的readline模块读取输入
const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let lines = [];
rl.on('line', (line) => {lines.push(line);// 当读取到两行输入时，调用函数输出结果if (lines.length === 2) {console.log(longestCommonSubstring(lines[0], lines[1]));rl.close();}
});

六、C算法源码

/*
C代码：使用动态规划寻找最长公共子串
编译时建议使用 -std=c99 标准
*/#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define MAX_LEN 1000  // 假设输入的最大字符串长度为1000int main() {char a[MAX_LEN], b[MAX_LEN];// 读取第一行和第二行输入fgets(a, MAX_LEN, stdin);fgets(b, MAX_LEN, stdin);// 去除末尾的换行符a[strcspn(a, "\n")] = '\0';b[strcspn(b, "\n")] = '\0';int m = strlen(a), n = strlen(b);// 动态分配二维数组dp，大小为(m+1) x (n+1)，所有元素初始化为0int **dp = (int **)malloc((m + 1) * sizeof(int *));for (int i = 0; i <= m; i++) {dp[i] = (int *)calloc(n + 1, sizeof(int));}int maxLen = 0;   // 记录最长公共子串的长度int endIndex = 0; // 记录最长公共子串在字符串a中的结束位置// 动态规划计算最长公共子串for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (a[i - 1] == b[j - 1]) {// 如果字符相同，dp[i][j]等于左上角dp值加1dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > maxLen) {maxLen = dp[i][j];endIndex = i;}}}}// 输出最长公共子串，如果maxLen为0则输出空字符串if (maxLen > 0) {char *result = (char *)malloc((maxLen + 1) * sizeof(char));strncpy(result, a + endIndex - maxLen, maxLen);result[maxLen] = '\0';printf("%s", result);free(result);}// 释放动态分配的内存for (int i = 0; i <= m; i++) {free(dp[i]);}free(dp);return 0;
}

七、C++算法源码

/*
C++代码：使用动态规划寻找最长公共子串
*/#include <iostream>
#include <string>
#include <vector>
using namespace std;int main() {string a, b;// 读取两行输入getline(cin, a);getline(cin, b);int m = a.size(), n = b.size();// 创建二维vector dp，大小为(m+1) x (n+1)，初始值均为0vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));int maxLen = 0;   // 记录最长公共子串的长度int endIndex = 0; // 记录最长公共子串在字符串a中的结束位置// 动态规划求解最长公共子串for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (a[i - 1] == b[j - 1]) {// 若当前字符相同，则dp[i][j]等于左上角dp值加1dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > maxLen) {maxLen = dp[i][j];endIndex = i;}}}}// 输出最长公共子串，如果maxLen为0则输出空字符串if (maxLen > 0) {cout << a.substr(endIndex - maxLen, maxLen);}return 0;
}