最长公共子串(动态规划)-Toy模板网

这篇具有很好参考价值的文章主要介绍了最长公共子串(动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

查找两个字符串a,b中的最长公共子串_牛客题霸_牛客网

1.找a 和 b 的最长公共子串实际上是在a的子串和b的子串中找最长公共子串

ins[i][j]实际上记录的就是以a的第i个字符和以b的第j个字符结尾的子串中存在的最长公共子串的长度

接下来我们举个例子:

a: abcabcde

b: abcd

ins[1][1] = 'a' 'a' --> 'a' 1

ins[2][2] = 'ab' 'ab' --> 'ab' 2

ins[3][3] = 'abc' 'abc' --> 'abc' 3

ins[4][4] = 'abca' 'abcd' --> 0

到了ins[4][4] 的我卡住了,当时想的是ins[4][4] 就是a的子串 abca b的子串abcd中存在的最长公共子串应该是abc 那么这个值是3 而不是0

我们先跳过一下:找一下这个整体规律:

如果以第i个字符结尾的字符和以第j个字符结尾的字符相等,那么

ins[i][j] = ins[i-1][j-1] + 1 (很明显前面三个都是满足的)

假如不相等,ins[i][j] = 0

但是为什么不是 ins[i][j] = ins[i-1][j-1]

接下来分析一下:实际上按照ins[4][4] = ins[3][3] = 3的说法是不完全准确的,为什么?

假设哈: a = abcdh

b = abcjh

ins[3][3] = 3

这里用假设性原则:ins[i][j] = ins[i-1][j-1]

ins[4][4] = ins[3][3] = 3

ins[5][5] = ins[4][4] +1 = 4

实际上呢??? ins[5][5] 的最常公共子串长度是3 ,这个我们一样就可以看出来,那么按照我们那种假设性原则导致了变成了求最长公共子序列的问题(也就是不连续即可)

除非你能保证你i j 不相等且是最后一个的时候才能说明 ins[i][j] = in[i-1][j-1],但是之前的是不行的

所以这个地方着重解释了当两个字符不相等的时候为什么不是ins[i][j] = ins[i-1][j-1]

2.那么ins[i][j] != ins[i-1][j-1] 究竟结果是啥呢??? 实际上这里你可以设置为0

因为你设置成0不影响结果得,你之前的ins[3][3] = 3实际上是把这个最长子串的长度记录下来了,不必去在ins[4][4] 里搅混水

当我们去遍历这个二维数组的时候,一定是记录下了这个最长子串,当你再去更新的时候就行

3.那么这个起始位置如何判断???

start = i - max, 我们是从短字符串来判定的, 你确定了这个最长子串,肯定是最后一个位置是

i 而且你的最后一个字符相等说明 i之前的max个字符都相等,那么从 (i - max,i)就是最长子串文章来源地址https://www.toymoban.com/news/detail-411095.html

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str = br.readLine())!=null){
            String ss = br.readLine();
            if(str.length()<ss.length()){
                System.out.println(res(str,ss));
            }else{
                System.out.println(res(ss,str));
            }
        }
    }
    public static String res(String s,String c){
        char[] ch1 = s.toCharArray();
        char[] ch2 = c.toCharArray();
        int[][] ins = new int[ch1.length + 1][ch2.length + 1];
        int max = 0;
        int start = 0;
        for (int i = 1; i < ch1.length; i++) {
            for (int j = 1; j < ch2.length; j++) {
                if(ch1[i-1]==ch2[j-1]){
                    ins[i][j] = ins[i-1][j-1]+1;
                    if(ins[i][j]>max){
                        max = ins[i][j];
                        start = i-max;
                    }
                }
            }
        }
        return s.substring(start,start+max);
    }
}

到了这里，关于最长公共子串(动态规划)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！