首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串

对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。

给定两个字符串A和B，同时给定两串的长度n和m。

测试样例：

"1AB2345CD",9,"12345EF",7

返回：4

算法知识视频讲解

重生之我要当分子

发表于 2025-01-01 00:19:29

解题思路这是一个最长公共子串问题。关键点：动态规划定义：表示以和结尾的最长公共子串长度注意与最长公共子序列的区别：子串必须连续状态转移：当时：否则：最终结果：需要记录数组中的最大值最大值即为最长公共子串的长度代码 cpp 展开全文

NiChangDance

发表于 2025-06-24 00:55:08

import java.util.*; public class LongestSubstring { public int findLongest(String A, int n, String B, int m) { // write code here 展开全文

I_wanna

发表于 2023-08-03 11:15:14

# -*- coding:utf-8 -*- class LongestSubstring: def findLongest(self, A, n, B, m): # write code here dp = [ [0 for _ in range(m+1) 展开全文

用心的布莱克刷牛客

发表于 2025-05-19 22:20:17

class LongestSubstring { public: int findLongest(string A, int n, string B, int m) { // write code here //动态规划，dp[i][j]代表以A[i-1]和B 展开全文

问题信息

贪心动态规划

来自：面试常考算法题(九)-...

难度：

89条回答 142收藏 37070浏览

查看代码

最长公共子串

扫一扫，把题目装进口袋