首页 > 其他分享 >【动态规划】最长公共子串

【动态规划】最长公共子串

时间:2024-02-05 11:16:13浏览次数:25  
标签:子串 int text 数组 公共 最长 dp

目录

题目

应用 1:最长公共子串

题目

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子串的长度。如果不存在 公共子串 ,返回 0 。

示例 1:

输入:text1 = "abcbcde", text2 = "bbcbce"
输出:4
解释:最长公共子串是 "bcbc" ,它的长度为 4 。

解题思路

我们使用动态规划求解,设 \(dp[i][j]\) 表示字符串 \(text_1\) 的前 \(i\) 个字符,与字符串 \(text_2\) 的前 \(j\) 个字符的最长公共子串,即子串 \(text_1[:i-1]\) 与子串 \(text_2[:j-1]\) 的最长公共子串的长度。

这里,我们假设字符串 \(text_1\) 和字符串 \(text_2\) 的长度分别为 \(m\)、\(n\)。

边界条件

显然,当其中一个数组长度为零时,它们的公共前缀为零,因此,初始条件为:

\[\begin{aligned} dp[i][0] &= 0, \quad 0 \le i \le m\\ dp[0][j] &= 0, \quad 0 \le j \le n \end{aligned} \]

状态转移

当两个字符串的长度大于 \(1\) 时,对于子串 \(text_1[:i-1]\) 与子串 \(text_2[:j-1]\) 的最后一个字符 \(text_1[i-1]\)、\(text_2[j-1]\) :

  • 如果 \(text_1[i - 1] = text_2[j - 1]\),那么,当前状态可以由前一个状态转移得到,此时,公共子串的长度较上一个状态增加了一个字符的长度;

  • 如果 \(text_1[i - 1] \ne text_2[j - 1]\),那么,以字符 \(text_1[i-1]\) 和字符 \(text_2[j-1]\) 结尾的子串没有公共前缀,此时,它们的最长公共子串长度为零。

因此,状态转移方程为:

\[dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1, &text_1[i-1] = text_2[j-1]\\ 0, & text_1[i - 1] \ne text_2[j - 1] \end{cases} \]

代码实现

class Solution {
    public int LongestCommonSubStr(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }
}

应用 2:Leetcode 718. 最长重复子数组

题目

718. 最长重复子数组

解题思路

代码实现

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1:

输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。

解题思路

方法一:动态规划

注意,这里的子数组是连续的子数组。

这里,我们假设数组 \(num1\) 和数组 \(num2\) 的长度分别为 \(m\)、\(n\)。

同时,假设 \(dp[i][j]\) 表示子数组 \(num1[0 \cdots i - 1]\) 和子数组 \(num2[0 \cdots j - 1]\) 的最长公共前缀。

初始条件

显然,当其中一个数组长度为零时,它们的公共前缀为零,因此,初始条件为:

\[\begin{aligned} dp[i][0] &= 0, \quad 0 \le i \le m\\ dp[0][j] &= 0, \quad 0 \le j \le n \end{aligned} \]

状态转移

当字符长度大于零时,我们可以考虑枚举其中一个数组的前缀,这里假设枚举前缀 \(num1[0 \cdots i - 1]\),那么,此时,我们只需要枚举另一个数组的前缀即可,只要某一个字符不相等,下一个位置的前缀就要从 \(0\) 开始计算。

即对于子数组 \(num1[0 \cdots i - 1]\) 和子数组 \(num2[0 \cdots j - 1]\):

  • 如果数字 \(num1[i - 1]\) 与数字 \(num2[j - 1]\)相等,那么,它们显然可以构成更长的数组前缀;

  • 如果它们不相等,那么,它们的公共前缀就为零。

因此,状态转移方程为:

\[dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1, &num1[i - 1] = num2[j - 1]\\ 0, & num1[i - 1] \ne num2[j - 1] \end{cases} \]

复杂度
  • 时间复杂度: \(O(n \times m)\)

  • 空间复杂度: \(O(n \times m)\)

方法二:滑动窗口

我们考虑使用滑动窗口的思路求解,我们以其中一个数组为基准,枚举它的起始位置,并求解它与另一个数组的最长公共前缀。

复杂度
  • 时间复杂度: \(O((m + n) \times min(m, n))\)

  • 空间复杂度: \(O(1)\)

代码实现

  • 方法一
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }
}
  • 方法二
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
            int n = nums1.length, m = nums2.length;
            int result = 0;
            for (int i = 0; i < n; i++) {
                int length = Math.min(m, n - i);
                int maxLength = getMaxLength(nums1, nums2, i, 0, length);
                result = Math.max(result, maxLength);
            }

            for (int i = 0; i < m; i++) {
                int length = Math.min(n, m - i);
                int maxLength = getMaxLength(nums1, nums2, 0, i, length);
                result = Math.max(result, maxLength);
            }
            return result;
        }

    private int getMaxLength(int[] a, int[] b, int i, int j, int length) {
        int result = 0, count = 0;
        for (int k = 0; k < length; k++) {
            if (a[i + k] == b[j + k]) {
                count++;
            } else {
                count = 0;
            }
            result = Math.max(result, count);
        }
        return result;
    }
}

标签:子串,int,text,数组,公共,最长,dp
From: https://www.cnblogs.com/larry1024/p/18007566

相关文章

  • 无重复字符的最长子串
    问题描述:给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。示例1:输入:"abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:"bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度为1。示例3:输入:......
  • 最小覆盖子串
    问题描述:给定一个字符串S和一个字符串T,请在S中找出包含T所有字母的最小子串。示例:输入:S="ADOBECODEBANC",T="ABC"输出:"BANC"说明:如果S中不存这样的子串,则返回空字符串""。如果S中存在这样的子串,我们保证它是唯一的答案。/***思路:*我们可以考......
  • Problem P06. [算法课分治] 找到 k 个最长重复字符串
    注意是在该子字符串内每个字符的出现次数都不少于k。可以采用分治的方法,函数找一个不符合条件的字符,然后将字符串分成两个子字符串,就这样进行递归运算,每次找到符合条件的子字符串就判断一波长度,然后将最长的长度值存下来。#include<iostream>#include<bits/stdc++.h>#includ......
  • 通过删除字母匹配到字典里最长单词
    问题描述:给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。示例1:输入:s="abpcplea",d=["ale","apple","monkey","plea"]......
  • hdu 4460 Friend Chains (图最长路的最小值)
    Problem-4460(hdu.edu.cn)写完提交答案错了,后面发现vis初始化的地方错了,以前BFS都只调用一次,看来我中毒太深。这个题更能体现BFS的特性,增加dis数组记录距离。#include<iostream>#include<queue>#include<cstring>#include<vector>#include<map>usingnamespacestd;c......
  • [IOI2023] 最长路程
    题目描述IOI2023组委会有大麻烦了!他们忘记计划即将到来的Ópusztaszer之旅了。然而,或许一切尚未为晚......在Ópusztaszer有\(N\)个地标,编号为从\(0\)到\(N-1\)。某些地标之间连有双向的道路。任意一对地标之间至多连有一条道路。组委会不知道哪些地标之间有道路相......
  • AcWing 520. 子串 题解
    ps:觉得这编号很特殊就做了一下题目传送门算法(线性DP,前缀和)\(O(nmk)\)首先考虑如何DP,然后再考虑如何优化。状态表示:f[i,j,k]表示只用S的前i个字母,选取了k段,可以匹配T的前j个字母的方案数。状态计算:将f[i,j,k]表示的所有方案分成两大类:不用S[i],则方案数是f[i-1,......
  • 最长上升子序列总结
    这是最长上升子序列最基础的例子:给定一串数字32451那么他的最长上升子序列就是345其衍生问题为:求最长递减子序列、求正方向反方向最长递增/递减子序列求先上升后下降的最长子序列、求能完全覆盖整个序列的最小下降子序列个数求能完全覆盖整个序列的最小上升和下降......
  • 最多提取子串数目 od
    最多提取子串数目最多提取子串数目题目给定由[a-z]26个英文小写字母组成的字符串A和B,其中A中可能存在重复字母,B中不会存在重复字母现从字符串A中按规则挑选一些字母,可以组成字符串B。挑选规则如下:1)同一个位置的字母只能被挑选一次2)被挑选字母的相对先后顺序不......
  • 【字符串】区间本质不同子串个数
    题目描述给定一个字符串\(S\),\(m\)次询问,每次询问\(S_{[l,r]}\)中有多少个本质不同的子串。\(1\leq|S|\leq10^5,1\leqm\leq2\times10^5\)。算法描述考虑HH的项链那道题,扫描右端点,维护对于某些串,能贡献的最大的左端点。假设有一个长为\(len\)的串,最后一次......