最大公共子串

[编程题]最大公共子串

热度指数：4089 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个字符串，请编写代码，输出最长公共子串（Longest Common Substring），是指两个字符串中的最长的公共子串，要求子串一定是连续。

数据范围：输入的两个字符串长度满足 $1 \le n \le 100 \$

输入描述:

文本格式，2个非空字符串（字母数字组成），2个字符串以","英文逗号分割。

输出描述:

整形，为匹配到的最长子串长度

示例1

输入

bab,caba

输出

算法知识视频讲解

Java

ccccdz

import java.util.*;
public class Main {
        public static void main(String [] args){
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){
                String[] str=sc.next().split(",");
                int max=0;
                for(int i=0;i<str[0].length();i++){
                    for(int j=i+1;j<=str[0].length();j++){
                        if(str[1].contains(str[0].substring(i,j))){
                            max=Math.max(max,str[0].substring(i,j).length());
                        }
                    }
                }
                System.out.println(max);
            }
        }
}

发表于 2020-08-05 20:09:20 回复(0)

Java

何止hz

dp经典题目

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 18:29
 * @Description: 最大公共子串
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] ss = sc.nextLine().split(",");
        int[][] dp = new int[ss[0].length()+1][ss[1].length()+1];
        int ans = 0;
        for (int i = 1; i <= ss[0].length(); i++)
            for (int j = 1; j <= ss[1].length(); j++){
                if (ss[0].charAt(i-1) == ss[1].charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        System.out.println(ans);
    }
}

发表于 2020-05-10 18:53:22 回复(0)