华为OD机试2025C卷-寻找相同子串[100分]（ Java _ Python3 _ C++ _ C语言 _ JsNode _ Go）实现100%通过率

个人主页深夜coding算法 专栏系列2026年华为最新OD机试题库详解 一次订阅永久解锁 | 持续更新100篇 | 6语言全覆盖文章目录❄️前言☀️一题目描述 题目名称 题目内容 输入描述 输出描述 示例☀️二解题思路☀️三代码实现CJavaPython3C语言JavaScriptGo☀️四复杂度分析⭐ 五易错点坑1子串和子序列搞混坑2一维DP倒序更新共勉❄️前言寻找相同子串是在两个字符串里找最长的公共子串。暴力O(N³)不好使动态规划O(N²)才是正解。记住dp[i][j]的含义以s1[i-1]和s2[j-1]结尾的最长公共子串长度。☀️一题目描述 题目名称寻找相同子串 题目内容给定两个字符串str1和str2求这两个字符串的最长公共子串的长度。子串要求在原字符串中是连续的。 输入描述第一行字符串 str1第二行字符串 str2字符串长度不超过 1000。 输出描述输出一个整数表示最长公共子串的长度。 示例输入 abcdef zbcde 输出 4 说明最长公共子串为 bcde长度为 4☀️二解题思路dp[i][j]以 s1[i-1] 和 s2[j-1]结尾的最长公共子串长度。若s1[i-1] s2[j-1]dp[i][j] dp[i-1][j-1] 1否则dp[i][j] 0答案 max(dp[i][j])可优化为一维DP。☀️三代码实现C#includeiostream#includestring#includevectorusingnamespacestd;intmain(){string s1,s2;getline(cin,s1);getline(cin,s2);intns1.size(),ms2.size(),ans0;vectorintdp(m1,0);for(inti1;in;i)for(intjm;j1;j--){// 倒序防覆盖if(s1[i-1]s2[j-1]){dp[j]dp[j-1]1;ansmax(ans,dp[j]);}elsedp[j]0;}coutansendl;}Javaimportjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Strings1sc.nextLine(),s2sc.nextLine();intns1.length(),ms2.length(),ans0;int[]dpnewint[m1];for(inti1;in;i)for(intjm;j1;j--){if(s1.charAt(i-1)s2.charAt(j-1)){dp[j]dp[j-1]1;ansMath.max(ans,dp[j]);}elsedp[j]0;}System.out.println(ans);}}Python3s1input().strip()s2input().strip()n,mlen(s1),len(s2)dp[0]*(m1)ans0foriinrange(1,n1):forjinrange(m,0,-1):ifs1[i-1]s2[j-1]:dp[j]dp[j-1]1ansmax(ans,dp[j])else:dp[j]0print(ans)C语言#includestdio.h#includestring.h#defineMAX(a,b)((a)(b)?(a):(b))intmain(){chars1[1024],s2[1024];gets(s1);gets(s2);intnstrlen(s1),mstrlen(s2),ans0,dp[1024]{0};for(inti1;in;i)for(intjm;j1;j--){if(s1[i-1]s2[j-1]){dp[j]dp[j-1]1;ansMAX(ans,dp[j]);}elsedp[j]0;}printf(%d\n,ans);}JavaScriptconst[s1,s2]require(fs).readFileSync(0,utf-8).trim().split(\n);constns1.length,ms2.length;constdpArray(m1).fill(0);letans0;for(leti1;in;i)for(letjm;j1;j--){if(s1[i-1]s2[j-1]){dp[j]dp[j-1]1;ansMath.max(ans,dp[j]);}elsedp[j]0;}console.log(ans);Gopackagemainimport(bufio;fmt;os)funcmain(){scanner:bufio.NewScanner(os.Stdin)scanner.Scan();s1:scanner.Text()scanner.Scan();s2:scanner.Text()n,m:len(s1),len(s2)dp:make([]int,m1)ans:0fori:1;in;i{forj:m;j1;j--{ifs1[i-1]s2[j-1]{dp[j]dp[j-1]1ifdp[j]ans{ansdp[j]}}else{dp[j]0}}}fmt.Println(ans)}☀️四复杂度分析指标数值时间复杂度O(N*M)空间复杂度O(min(N,M))一维优化后⭐ 五易错点坑1子串和子序列搞混子串必须连续子序列不用。dp不匹配时归零是子串的关键。坑2一维DP倒序更新正序会读到本轮的dp[j-1]而非上轮的所以必须从右往左更新。共勉最长公共子串是DP经典款一维优化倒序更新面试常考。关于本专栏一次订阅永久解锁全部100篇真题详解6语言全覆盖Java | Python3 | C | C语言 | JsNode | Go