首页 > 试题广场 >

公共子串计算

[编程题]公共子串计算

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

$\hspace{15pt}$ 对于给定的两个字符串 $s$ 和 $t$ ，你需要找出它们的最长公共子串的长度。

$\hspace{15pt}$ 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
$\hspace{15pt}$ 如果字符串 $a$ 的一个子串 $a'$ 与字符串 $b$ 的一个子串 $b'$ 完全相等，那么子串 $a',b'$ 是字符串 $a,b$ 的一个公共子串。

输入描述:

$\hspace{15pt}$ 第一行输入一个长度为 $1 \leqq {\rm len}(s) \leqq 150$ 、仅由小写字母组成的字符串 $s$ 。
$\hspace{15pt}$ 第二行输入一个长度为 $1 \leqq {\rm len}(t) \leqq 150$ 、仅由小写字母组成的字符串 $t$ 。

输出描述:

$\hspace{15pt}$ 输出一个整数，代表 $s$ 和 $t$ 的最长公共子串的长度。

示例1

输入

awaabb
aawbb

输出

说明

在这个样例中， 和  都是  和  的最长公共子串。

示例2

输入

asdfas
werasdfaswer

输出

算法知识视频讲解

Java

牛客281381469号

动态规划题目，dp[i][j]含义为以i - 1为结尾的str1和以j - 1为结尾的str2的最长公共子串，这样可以避免判断第一个串的第一个字符和第二个串的字符是否相等。当str1.charAt(i - 1)和str2.charAt(j - 1)相等时，dp[i][j]和dp[i - 1][j - 1] + 1取最大值。随时遍历dp[i][j]的最值，最后返回给控制台即可。7.17
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
            int max = 0;
            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] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                        max = Math.max(max, dp[i][j]);
                    }
                }
            }
            System.out.println(max);
        }
    }
}

发表于 2025-07-17 20:51:32 回复(1)

Java

细致的勇士求对象

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String stra = sc.next();
        String strb = sc.next();
        int a = stra.length();
        int b = strb.length();
        int maxLength = 0;//定义初始公共子串长度为0
        int shorterLen = a < b ? a : b;//定义较短字符串的长度

        for (int i = 1; i <= shorterLen; i++) {
            //不区分长短字符串,直接遍历a字符串的所有子串与b比较
            // (限定了较短字符串长度shorterLen,不怕超出范围)
            for (int j = 0; j <= a - i; j++) {
                //i是子串长度, j是子串起始位置
                String str = stra.substring(j, j + i);
                //截取尾索引为stra的长度,因此j+i<=a,j<=a-i
                if (strb.contains(str)) {
                    maxLength++;
                    //找到一次即跳出循环,继续找下一个子串
                    break;
                }
            }

        }
        System.out.println(maxLength);
    }

}

发表于 2025-06-03 12:51:53 回复(0)

Java

fulai

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            System.out.println(getMaxSubString(a, b));
        }
    }

    private static int getMaxSubString(String a, String b) {
        int len1 = a.length();
        int len2 = b.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        int max = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return max;
    }
}

发表于 2025-02-05 21:32:20 回复(0)

Java

段航舟

看着讨论区的代码好复杂

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String str1 = in.nextLine();
		String str2 = in.nextLine();
		int maxLength = 0;
		for (int i = 0; i < str1.length(); i++) {
			for (int j = i; j < str1.length(); j++) {
				String substring = str1.substring(i, j + 1);//j + 1需要包含最后一位
				if (str2.contains(substring)) {
					maxLength = Math.max(maxLength, substring.length());
				}
			}
		}
		System.out.println(maxLength);
		in.close();
	}
}

发表于 2024-09-28 11:57:25 回复(0)

Java

牛客201673936号

import java.util.*;
//动态规划
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int len1 = str1.length();
        int len2 = str2.length();
        //状态方程dp[i][j]：字符串1长度为i，字符串2长度为j时最长公共字串长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        int max = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    //动规表达式,本组相等取前一组相等的长度加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2024-09-10 15:15:31 回复(0)

Java

牛客248641941号

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String str1 = in.nextLine();

String str2 = in.nextLine();

int length = 0;

for (int i =0; i<str2.length(); i++){

for (int j=0; j<str2.length()-i; j++){

String substring = str2.substring(i, str2.length()-j);

if (str1.contains(substring)){

if (length < substring.length()){

length = substring.length();

}

System.out.println(length);

}

发表于 2024-08-02 23:35:45 回复(2)

Java

ZXiaolon

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int res=0;

String s1=in.nextLine();

String s2=in.nextLine();

in.close();

// 暴力解

int res1=comstr(s1,s2);

int res2=comstr(s2,s1);

System.out.println(Math.max(res1,res2));

}

public static int comstr(String s1,String s2){

int res=0;

int len1=s1.length();

int len2=s2.length();

for(int i=0;i<len1;i++){

int temp=0;

for(int j=0;j<len2 && (i+j)<len1;j++){

if(s1.charAt(i+j)==s2.charAt(j)){

temp++;

if(temp>res){

res=temp;

}

else{

temp=0;

}

return res;

}

编辑于 2024-04-10 21:48:40 回复(0)

Java

牛客658252555号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

String str1 = in.nextLine();

String str2 = in.nextLine();

String max = "";

String min = "";

max = (str1.length() > str2.length()) ? str1: str2;

min = (max == str1)? str2: str1;

//System.out.println(max);

//System.out.println(min);

for(int i = min.length(); i>=1; i-- ) {

for(int j = 0,n=i; j<= min.length()-i; j++, n++) {

String sub = min.substring(j, n);

//System.out.println("i: " + i + " j: " +j +" sub: " +sub);

if(max.contains(sub)) {

//System.out.println("contains");

System.out.println(sub.length());

return;

}

System.out.println(0);

}

发表于 2023-10-27 21:30:20 回复(0)

Java

Yhejun

import java.util.Scanner;

import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        if(str1.length()>str2.length()){
            String str =str1;
            str1 = str2;
            str1 = str;
        }
        if(str2.contains(str1)){
            System.out.println(str1.length());
            return;
        }
        for(int i = 1;i<str1.length();i++){
            for(int j = 0;j<=i;j++){
                String str;
                str = str1.substring(j,str1.length()-(i-j));
                if(str2.contains(str)){
                    System.out.println(str.length());
                    return;
                }
            }
        }
        System.out.println(0);
    }
}

19ms,求大佬分析为啥比榜上的慢这么多

发表于 2023-09-21 16:13:18 回复(0)

Java

牛客106397800号

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1 = br.readLine();
        String line2 = br.readLine();

        // 找出短的字符串
        String shortStr = line1.length() <= line2.length() ? line1 : line2;
        String longStr = line1.length() <= line2.length() ? line2 : line1;

        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < shortStr.length(); i++) {
            for (int j = i + 1; j <= shortStr.length(); j++) {
                String sub = shortStr.substring(i, j);
                if (longStr.contains(sub)) {
                    map.put(sub, sub.length());
                }
            }
        }

        // 计算最大长度
        if (map.size() > 0) {
            Collection<Integer> values = map.values();
            int max = Collections.max(values);
            System.out.println(max);
        } else {
            System.out.println(0);
        }

    }
}

发表于 2023-08-12 12:08:45 回复(0)

Java

大凡牛牛牛

import java.util.*;

//动态规划

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String str1=sc.nextLine();

String str2=sc.nextLine();

int len1=str1.length();

int len2=str2.length();

//状态方程dp[i][j]：字符串1长度为i，字符串2长度为j时最长公共字串长度

int[][] dp=new int[len1+1][len2+1];

int max=0;

for(int i=1;i<=len1;i++){

for(int j=1;j<=len2;j++){

if(str1.charAt(i-1)==str2.charAt(j-1)){

dp[i][j]=dp[i-1][j-1]+1;

max=Math.max(max,dp[i][j]);

}

System.out.println(max);

}

发表于 2023-07-19 18:04:53 回复(0)

Java

牛客748979364号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

String a=in.next();

String b=in.next();

String c;

int length=0;

for(int i=0;i<a.length();i++)

{for(int d=0;d<a.length()-i;d++)

{ c=a.substring(d,i+d+1);

if(b.contains(c)&&length<c.length())

{

length=c.length();

}

System.out.print(length);

}

发表于 2023-07-13 17:29:13 回复(0)

Java

练习时长两年半的太平湖水怪很理智

import java.io.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String str1=br.readLine();
        String str2=br.readLine();
        int len1=str1.length();
        int len2=str2.length();
        //记录str1的第i字符和str2的第j字符的最长公共子串长度
        int[][] dp = new int[len1+1][len2+1];
        //maxLCS记录最终的最长公共子串长度
        int maxLCS=0;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                //str1.charAt(i-1)==str2.charAt(j-1)时，最长公共子串长度dp[i][j]等于没有str1的第i
                //字符和str2的第j字符参与比较时的最长公共子串长度+1
                if(str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
                if(dp[i][j]>maxLCS) maxLCS=dp[i][j];
            }
        }
        System.out.println(maxLCS);
    }
}

发表于 2023-07-05 18:33:46 回复(0)

Java

一二三四五lhs

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextLine()) { // 注意 while 处理多个 case

String str1 = in.nextLine();

String str2 = in.nextLine();

System.out.println(funHJ75(str1, str2));

}

public static int funHJ75(String str1, String str2) {

int result = 0;

String max = str1.length() >= str2.length() ? str1 : str2;

String min = str1.length() >= str2.length() ? str2 : str1;

//i表示substring的跨度，j表示从哪一位开始切片，暴力遍历破解

for (int i = 1; i <= min.length(); i++) {

for (int j = 0; i + j <= min.length(); j++) {

String temp = min.substring(j, j + i);

if (max.contains(temp)) {

result = temp.length();

break;

}

return result;

}

发表于 2023-06-17 15:29:51 回复(0)

提交观点

问题信息

动态规划字符串查找

难度：

75条回答 2245收藏 51060浏览

通过挑战的用户

查看代码

牛客46027...

2023-03-04 10:16:08
36度的手指编程

2023-02-27 16:21:07
牛客80860...

2023-02-20 20:58:38
爱看剧的芹菜爱读书

2022-11-09 12:07:56
杉烟茗茗

2022-11-08 21:03:51

公共子串计算

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题