最长公共子串

阳光穿透心脏的1/2处 2022-10-29 11:17 120阅读 0赞

/** * 求最长公共子串 */
    public class Solution8 { 
        public static void main(String[] args) { 
            String str1 = "babce";
            String str2 = "eeeebce";
            int i = maxLength(str1, str2);
            System.out.println(i);
        }
    
        /** * dp[i][j]是str1[0...i-1]和str2[0...j-1]的最长公共子串的长度 */
        static int maxLength(String str1, String str2) { 
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
            for (int i = 0; i <= str1.length(); i++) { 
                dp[i][0] = 0;
            }
            for (int j = 0; j < str2.length(); j++) { 
                dp[0][j] = 0;
            }
            int res = Integer.MIN_VALUE;
            for (int i = 1; i <= str1.length(); i++) { 
                for (int j = 1; j <= str2.length(); j++) { 
                    if (str1.charAt(i-1) == str2.charAt(j-1)) { 
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }
                    res = Math.max(res, dp[i][j]);
                }
            }
            return res;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关最长公共子串

题目： [\[编程题\]最长公共子串][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

男娘i/ 2022年12月07日 15:23/ 0 赞/ 139 阅读

相关【Java】最长公共子串

Scanner in = new Scanner(System.in); while (in.hasNextLine()) {

喜欢ヅ旅行/ 2022年11月11日 10:50/ 0 赞/ 129 阅读

相关最长公共子串

/ 求最长公共子串 / public class Solution8 { public static void main(String[]

阳光穿透心脏的1/2处/ 2022年10月29日 11:17/ 0 赞/ 121 阅读

相关最长公共子串

[lintcode练习题目][lintcode] include "string" include "stdio.h" include "iostre

ゝ一世哀愁。/ 2022年09月24日 12:23/ 0 赞/ 133 阅读

相关最长公共子串与最长连续子串算法

利用DP思想最长公共子串中result\[i\]\[j\]存放str1前i个与result\[j\]个的最长公共子串，当str1\[i + 1\]==str2\[j + 1

男娘i/ 2022年08月11日 16:44/ 0 赞/ 164 阅读

相关求最长公共子串

文章目录求最长公共子串思路一思路二思路三求最长公共子串最长公共子串最好的算法是动态规划。其次KMP

你的名字/ 2022年02月01日 15:15/ 0 赞/ 207 阅读

相关最长公共子串

最长公共子串（注意子串是连续的，也是与最长公共子序列的区别） 1、先建立一个二维数组array\[str1.size()\]\[str2.size()\]（全部初始化为0

秒速五厘米/ 2021年10月19日 05:48/ 0 赞/ 310 阅读

相关最长公共子串问题

采用动态规划的思想。使用二维数组，每个元素dp\[i\]\[j\]表示以 A\[i-1\] B\[j - 1\]结尾的最大公共子串 import java.ut

ゝ一世哀愁。/ 2021年09月27日 06:16/ 0 赞/ 249 阅读

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

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

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