首页 > 试题广场 >

公共子串计算

[编程题]公共子串计算

热度指数：196572 时间限制：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

细致的勇士求对象

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)

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;
        //表示str1的i位置和str2的j位置时候，最长公共子串的长度为dp[i+1][j+1];
        int dp[][]=new int[str1.length()+1][str2.length()+1];
        for(int i=0;i<str1.length();i++){
            for(int j=0;j<str2.length();j++){
                //如果字符相等的时候
                if(str1.charAt(i)==str2.charAt(j)){
                    //维护dp数组，使其最长长度为i-1,j-1的位置长度+1
                    dp[i+1][j+1]=dp[i][j]+1;
                    //维护最大长度
                    if(dp[i+1][j+1]>maxLength){
                        maxLength=dp[i+1][j+1];
                    }
                    //不等说明当前位置最大长度为0
                }else{
                    dp[i+1][j+1]=0;
                }
            }
        }
        System.out.print(maxLength);
    }
}

发表于 2023-06-06 08:40:22 回复(0)

提交观点

问题信息

动态规划字符串查找

难度：

74条回答 2186收藏 48769浏览

通过挑战的用户

查看代码

牛客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

公共子串计算

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题