lintcode 79. 最长公共子串动态规划

布满荆棘的人生 2023-07-03 10:32 13阅读 0赞

给出两个字符串，找到最长公共子串，并返回其长度。

样例
    样例 1:
    	输入:  "ABCD" and "CBCE"
    	输出:  2
    	
    	解释:
    	最长公共子串是 "BC"
    
    
    样例 2:
    	输入: "ABCD" and "EACB"
    	输出:  1
    	
    	解释: 
    	最长公共子串是 'A' 或 'C' 或 'B'
    挑战
    O(n x m) time and memory.
    
    注意事项
    子串的字符应该连续的出现在原字符串中，这与子序列有所不同。

class Solution {
        
    public:
        /**
         * @param A: A string
         * @param B: A string
         * @return: the length of the longest common substring.
         */
        int longestCommonSubstring(string &A, string &B) {
        
            // write your code here
            int n1=A.size();
            int n2=B.size();
            if(n1==0||n2==0) return 0;
            vector<vector<int>>  dp(n1+1,vector<int>(n2+1,0));
            int max=-1;
            for (int i = 1; i <= n1; i++) {
        
                /* code */
                for (int j = 1; j <= n2; j++) {
        
                    /* code */
                    if(A[i-1]==B[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                    max=max>dp[i][j]?max:dp[i][j];
                }
            }
            return max;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关 [动态规划][公共子串]最长公共子串、最长公共子序列

1、最长公共子串 LintCode：[https://www.lintcode.com/problem/longest-common-substring/descri...

约定不等于承诺〃/ 2024年04月18日 17:10/ 0 赞/ 74 阅读

相关面试（动态规划算法之：最长公共子序列 & 最长公共子串（LCS））

收藏 1、先科普下最长公共子序列 & 最长公共子串的区别：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共

迷南。/ 2023年10月17日 14:00/ 0 赞/ 67 阅读

相关 lintcode 79. 最长公共子串动态规划

给出两个字符串，找到最长公共子串，并返回其长度。样例样例 1: 输入: "ABCD" and "CBCE" 输出: 2

布满荆棘的人生/ 2023年07月03日 10:32/ 0 赞/ 14 阅读

相关【动态规划】求最长公共子串，最长回文子串

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。 eg : fbaabe，ebaabf，连续最长子串长度为4。注意：求最长回文子串也可以用求最长公

朴灿烈づ我的快乐病毒、/ 2022年08月09日 00:59/ 0 赞/ 275 阅读

相关动态规划：求最长公共子串/最长公共子序列

最长公共子序列和最长公共子串区别最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence

我不是女神ヾ/ 2022年08月08日 03:24/ 0 赞/ 280 阅读

相关最长公共子串（动态规划）

描述：计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。输入：输入两个字符串输出：输出一个整数样

迷南。/ 2022年06月08日 10:07/ 0 赞/ 237 阅读

相关动态规划---求最长公共子序列和最长公共子串（C语言）

参考：[https://blog.csdn.net/someone\_and\_anyone/article/details/81044153][https_blog.csdn

阳光穿透心脏的1/2处/ 2022年02月20日 07:08/ 0 赞/ 283 阅读

相关动态规划问题 —— 最长公共子串

题目描述链接：[https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602][

系统管理员/ 2022年02月17日 01:41/ 0 赞/ 265 阅读

相关动态规划最长公共子串

核心思路和最长公共子序列一样区别在于子串必须连续可以先看我之前这篇文章 [最长公共子序列问题总结][Link 1] 最长公共子串同样是构造二维数组存储最大值，只不过去

我就是我/ 2021年08月11日 20:24/ 0 赞/ 423 阅读

相关【动态规划】最长公共子序列与最长公共子串

[来源][Link 1] 1. 问题描述子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串 cnblogs belong 比如序列

「爱情、让人受尽委屈。」/ 2021年06月24日 16:12/ 0 赞/ 545 阅读