首页 > 试题广场 >

查找两个字符串a,b中的最长公共子串

[编程题]查找两个字符串a,b中的最长公共子串

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

$\hspace{15pt}$ 对于给定的两个字符串 $s$ 和 $t$ ，你需要找出它们的最长公共子串。特别地，如果存在多个答案，输出在较短串中最先出现的那个。

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

输入描述:

第一行输入一个长度为 、仅由小写字母组成的字符串 。
第二行输入一个长度为 、仅由小写字母组成的字符串 。

输出描述:

输出一个字符串，代表  和  的最长公共子串。如果存在多个答案，输出在较短串中最先出现的那个。

示例1

输入

awaabb
aawbb

输出

aa

说明

在这个样例中， 和  都是  和  的最长公共子串，但  在较短串  中首先出现，因此输出 。

示例2

输入

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出

jklmnop

算法知识视频讲解

Java

Sen🍓🍀

暴力破解竟然没超时

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.next(); // 长
        String s2 = in.next(); // 短
        if (s1.length() < s2.length()) { // 保证s2短
            String t = s1;
            s1 = s2;
            s2 = t;
        }

        for (int d = s2.length(); d > 0; d--) {  // d 即子串长度，从大到小，找到匹配的即所求
            for (int i = 0; i + d <= s2.length(); i++) { // 从左到右 扫描s2子串
                String sb = s2.substring(i, i + d);
                if (s1.length() - s1.replace(sb, "").length() > 0) { // s1含子串sb？
                    System.out.print(sb);
                    return; // 直接返回
                }
            }
        }
    }
}

发表于 2025-01-28 12:07:41 回复(0)

Java

牛客160935469号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        String l = a.length() > b.length()? a: b;
        String s = a.length() > b.length()? b: a;
        int max = 0, index = -1;
        for (int i = 1; i <= s.length(); i++) {  // 截取子串长度
            for (int j = 0; j <= s.length()-i; j++) {  // 短串
                for (int k = 0; k <= l.length()-i; k++) {  // 长串
                    if (l.substring(k, k+i).equals(s.substring(j, j+i))) {
                        if (max < i) {
                            index = j;
                            max = i;
                        }
                    }
                }
            }
        }
        if (index == -1) {
            System.out.println(-1);
        } else {
            System.out.println(s.substring(index, index + max));
        }
    }
}

发表于 2024-10-01 21:03:17 回复(0)

Java

牛客201673936号

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.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            if (a.length() < b.length()) {
                String temp = a;
                a = b;
                b = temp;
            }
            //保存最长子串的长度和索引
            int[] max = {0, 0};
            //创建临时表保存a[j-1]和b[i-1]的值
            int[][] length = new int[b.length() + 1][a.length() + 1];
            for (int i = 1; i <= b.length(); i++) {
                for (int j = 1; j <= a.length(); j++) {
                    if (a.charAt(j - 1) == b.charAt(i - 1)) {
                         //dp公式 当a[j]等于b[a]时，找到a[j-1]和b[i-1]的值加1
                        length[i][j] = length[i - 1][j - 1] + 1 ;
                        //判断这个子串是否为最长子串
                        if (max[0] < length[i][j]) {
                            max[0] = length[i][j]  ;
                            max[1] = i;
                        }
                    } else {
                        length[i][j] = 0;
                    }
                }
            }
            System.out.println(b.substring(max[1] - max[0], max[1]));
        }
    }
}

发表于 2024-09-09 21:17:37 回复(0)

Java

LY先生

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.nextLine();

String b = in.nextLine();

String shortString = a.length() > b.length() ? b : a;

String longString = a.length() > b.length() ? a : b;

int left = 0;

String str = "";

for (left = 0; left < shortString.length(); left++) {

int right = shortString.length();

while (left < right) {

String substring = shortString.substring(left, right);

if (longString.contains(substring) && substring.length() > str.length()) {

str = substring;

}

right--;

}

System.out.println(str);

}

发表于 2024-08-04 16:41:25 回复(0)

Java

牛客76365361号

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        if(a.length() > b.length()){
            String temp = a;
            a = b;
            b = temp;
        } // make sure a is the shorter string
        int n = a.length(); // n <= m
        int m = b.length();
        int[][] lccs = new int[n][m];
        for (int i = 0; i < n; i++) {
            lccs[i][0] = a.charAt(i) == b.charAt(0) ? 1 : 0;
        }
        for (int i = 0; i < m; i++) {
            lccs[0][i] = a.charAt(0) == b.charAt(i) ? 1 : 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++){
                if(a.charAt(i) == b.charAt(j)){
                    lccs[i][j] = lccs[i-1][j-1] + 1;
                } else {
                    lccs[i][j] = 0;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                max = Math.max(max, lccs[i][j]);
            }
        }
        // get the lccs earlist appear
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++){
                if(lccs[i][j] == max){
                    System.out.println(a.substring(i - max + 1, i + 1));
                    return;
                }
            }
        }
    }
}

实在不会写了……

发表于 2024-06-23 22:12:52 回复(0)

Java

FredtoCode

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

while (scanner.hasNext()) {

String str1 = scanner.nextLine();

String str2 = scanner.nextLine();

String temporary;

if (str1.length() > str2.length()) {

temporary = str2;

str2 = str1;

str1 = temporary;

}

int max = 0;

int index = 0;

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

if (str2.contains(str1.substring(i - max, i + 1))) {

max++;

index = i;

}

System.out.println(str1.substring(index - max + 1, index + 1));

}

编辑于 2024-04-05 17:29:39 回复(0)

Java

香辣素毛肚

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String s1 = in.nextLine();

String s2 = in.nextLine();

int index = 0;

int max = 0;

if (s1.length() > s2.length()) {

String tmp = s1;

s1 = s2;

s2 = tmp;

}

//不需要考虑初始化问题，dp[0][j]和dp[i][0]都是0

int[][] dp = new int[s1.length() + 1][s2.length() + 1];

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

for (int j = 1; j <= s2.length(); j++) {

if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

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

if (max < dp[i][j]) {

index = i - 1;//索引

max = dp[i][j];

}

// } else {

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

}

System.out.println(s1.substring(index - max + 1, index + 1));

}

参考的前排的代码，其实这个注释才是精髓。

最开始我是加了注释的，跑不出来，左思右想，原来是dp[i][j]表示从某个字符到i对于的串，要和某个字符到j的串完全相等

比如abcdf和abcef，当索引移动到d和e时,当前的公共子串长度为0，而不是3

编辑于 2024-03-25 11:42:12 回复(0)

Java

山里灵活的狗123

写段垃圾代码

时间复杂度 $图片说明$

空间复杂度 $图片说明$

import java.util.*;

// Class name must be XXmain, Dont have any package xxx info
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Attention difference between hasNext and hasNextLine
        char[] str1 = in.next().toCharArray();
        char[] str2 = in.next().toCharArray();
        if (str2.length > str1.length) {
            char[] temp = str1;
            str1 = str2;
            str2 = temp;
        }
        int[][] dp = new int[str1.length + 1][str2.length + 1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        int max = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max= Math.max(max, dp[i][j]);
                    int finalJ = j;
                    map.compute(dp[i][j], (k, v) -> {
                        if (v == null) {
                            v = new ArrayList<>();
                        }
                        v.add(finalJ);
                        return v;
                    });
                }
            }
        }
        List<Integer> indexes = map.get(max);
        Integer res = indexes.get(0);
        for (int i = 1; i < indexes.size(); i++) {
            Integer curr = indexes.get(i);
            if (curr < res) {
                res = curr;
            }
        }
        System.out.println(new String(str2).substring(res - max, res ));
    }
}

编辑于 2024-03-24 12:13:50 回复(1)

Java

锰锰在睡觉

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

String a = in.nextLine();

String b = in.nextLine();

if (a.length() > b.length()) {

String c = a;

a = b;

b = c;

}

String result = "";

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

for (int j = a.length() ; j > i; j--) {

if (b.contains(a.substring(i, j))&&a.substring(i, j).length()>result.length()) {

result = a.substring(i, j);

break;

}

System.out.println(result);

}

发表于 2023-09-26 15:59:18 回复(0)

Java

牛客553955499号

import java.util.Scanner;

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

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String first = in.nextLine();

String second = in.nextLine();

String shortStr = first.length()<second.length() ? first:second;

String longStr = first.length()<second.length() ? second:first;

int left = 0;

int len = 0;

int start=0,end =0;

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

String str = shortStr.substring(left,i);

if(longStr.indexOf(str)==-1){

left++;

}else{

if(str.length() > len){

len = str.length();

start = left;

end = i;

}

System.out.println(shortStr.substring(start,end));

}

发表于 2023-09-12 11:19:56 回复(0)

Java

GCID

DP[i][j] 存储A[I-1]与B[j-1]各自作为字串末尾进行匹配可能的最大长度。每次计算出DP[i][j]时更新全局结果。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] A=in.nextLine().toCharArray();
        char[] B=in.nextLine().toCharArray();
        if(A.length>B.length){
            char[] tmp=A;
            A=B;
            B=tmp;
        }
        int[][] DP=new int[A.length+1][B.length+1];

        
        int index=0;
        int n=0;
        for(int i=0;i<=A.length;i++){
            for(int j=0;j<=B.length;j++){
                if(i>0&&j>0){
                    if(A[i-1]==B[j-1]){
                        DP[i][j]=DP[i-1][j-1]+1;
                    }else{
                        DP[i][j]=0;
                    }

                    if(DP[i][j]>n){
                        n=DP[i][j];
                        index=i-n;  //A中的尾index=i-1,则字串长n时，首index=index-n+1=i-n
                    }

                }
            }
        }
        for(int i=0;i<n;i++){
            System.out.print(A[index+i]);
        }


    }
}

发表于 2023-09-08 15:39:29 回复(0)

Java

牛客106397800号

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
// 注意类名必须为 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 minLenStr = line1.length() <= line2.length() ? line1 : line2;
        String maxLenStr = line1.length() > line2.length() ? line1 : line2;

        // 最大子串
        String maxSubStr = "";
        for (int i = 0; i < minLenStr.length(); i++) {
            for (int j = i + 1; j <= minLenStr.length(); j++) {
                String sub1 = minLenStr.substring(i, j);
                if (maxLenStr.contains(sub1) && sub1.length() > maxSubStr.length()) {
                    maxSubStr = sub1;
                }
            }
        }

        System.out.println(maxSubStr);
    }
}

发表于 2023-08-11 10:40:45 回复(0)

Java

我是小韩

方法有很多吗，随便整
方法一(做完之后，看了官方题解重写的)：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String target = scanner.next();
            String source = scanner.next();
            if (target.length() > source.length()) {
                System.out.println(maxLengthSubString(target, source));
            } else {
                System.out.println(maxLengthSubString(source, target));
            }
        }
    }
    private static String maxLengthSubString(String source, String target) {
        int maxLength = 0;
        int start = 0;
        for (int i = 0; i < target.length(); i++) {
            if (target.length() - i + 1 < maxLength) {
                break;
            }
            // 剪枝，向左边靠近
            for (int k = target.length(); k > i; k-- ) {
                String subString = target.substring(i, k);
                // 因为向左边逼近，所有是最长的
                if (source.contains(subString) && subString.length() > maxLength) {
                    maxLength = subString.length();
                    start = i;
                    break;
                }
            }
        }
        return target.substring(start, start + maxLength);
    }
}

方法二:

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String target = scanner.next();
            String source = scanner.next();
            if (target.length() > source.length()) {
                System.out.println(maxLengthSubString(target, source));
            } else {
                System.out.println(maxLengthSubString(source, target));
            }
        }
    }

    private static String maxLengthSubString(String source, String target) {
        String maxSubString = "";
        for (int i = 0; i < target.length(); i++) {
            char current = target.charAt(i);
            int index = source.indexOf(current);
            while (index > -1) {
                int j = i;
                int temp = index;
                StringBuilder builder = new StringBuilder();
                while (temp < source.length() && j < target.length()) {
                    char node = target.charAt(j);
                    if (source.charAt(temp) != node) {
                        break;
                    }
                    builder.append(node);
                    temp++;
                    j++;
                }
                if (builder.length() > maxSubString.length()) {
                    maxSubString = builder.toString();
                }
                index = source.indexOf(current, index + 1);
            }
        }
        return maxSubString;
    }

发表于 2023-05-16 07:43:02 回复(1)

Java

牛客604637229号

String a = in.next();

String b = in.next();

String shortStr = "";

String longStr = "";

if (a.length() >= b.length()) {

shortStr = b;

longStr = a;

} else {

shortStr = a;

longStr = b;

}

String str = null;

TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();

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

for (int j = shortStr.length(); j >= i; j--) {

str = shortStr.substring(i, j);

if (longStr.contains(str)) {

if(!treeMap.containsKey(str.length())){

treeMap.put(str.length(),str);

}

if(str!=null){

System.out.println(treeMap.lastEntry().getValue());

}else{

System.out.println("");

}

发表于 2023-04-12 22:41:27 回复(0)

Java

打不死的小伍六七

import java.util.*;

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

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

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

String s1 = in.nextLine();

String s2 = in.nextLine();

String shortStr = s1.length() < s2.length() ? s1 : s2;

String longStr = s1.length() > s2.length() ? s1 : s2;

int max = 0;

HashMap<Integer, String> map = new HashMap<>();

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

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

String sub = shortStr.substring(i, j);

if (longStr.contains(sub)) {

if (sub.length() > max) {

max = sub.length();

map.put(max, sub);

}

System.out.println(map.get(max));

}

发表于 2023-04-01 18:38:13 回复(0)

Java

小熊爱找工作吖

import java.util.*;

查找两个字符串a,b中的最长公共子串

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {

String str1 = sc.nextLine();

String str2 = sc.nextLine();

int len1 = str1.length(); //较短

int len2 = str2.length(); //较长

//交换

if (len1 > len2) {

String tmp = str1;

str1 = str2;

str2 = tmp;

}

// System.out.println(solve(str1, str2));

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

}

//动归

public static String solve(String str1, String str2) {

int [][]dp = new int[str1.length() + 1][str2.length() + 1];

int max = 0, start = 0;

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

for (int j = 1; j < str2.length() + 1; j++) {

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

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

if (dp[i][j] > max) {

max = dp[i][j];

start = i - max;

}

return str1.substring(start, start + max);

}

//遍历

public static String solve1(String str1, String str2) {

int start = 0;

int max = 0;

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

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

if (str2.contains(str1.substring(i, j + 1))) {

if (str1.substring(i, j + 1).length() > max) {

max = str1.substring(i, j + 1).length();

start = i;

}

return str1.substring(start, start + max);

}

发表于 2023-03-27 16:01:31 回复(0)

Java

树荫下的天空

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()) {
            // 注意 hasNext 和 hasNextLine 的区别
            String a = in.nextLine();
            String b = in.nextLine();
            int m = a.length();
            int n = b.length();
            int[][] dp = new int[m + 1][n + 1];
            int maxLength = 0;
            int maxI = 0, maxJ = 0;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (a.charAt(i - 1) == b.charAt(j - 1)) {
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                        if (dp[i][j] > maxLength) {
                            maxLength = dp[i][j];
                            maxI = i;
                            maxJ = j;
                        } else if (dp[i][j] == maxLength) {
                            if (m < n && maxI > i || n < m && maxJ > j) {
                                maxI = i;
                                maxJ = j;
                            }
                        }
                    }
                }
            }

            System.out.println(a.substring(maxI - maxLength, maxI));
        }
    }
}

发表于 2022-11-02 20:55:12 回复(0)

Java

苏珊树脂666

运行时间：15ms
超过95.83% 用Java提交的代码
占用内存：9692KB
超过94.02% 用Java提交的代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine(), b = br.readLine(), maxSub = "";
        int len = a.length(), len2 = b.length();
        if (len > len2) {
            String temp = a;
            a = b;
            b = temp;
            len = len2;
        }
        
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                String sub = a.substring(i, j + 1);
                if (!b.contains(sub)) {
                    break;
                } else {
                    if (sub.length() > maxSub.length()) {
                        maxSub = sub;
                    }
                }
            }
        }
        System.out.println(maxSub);
    }
}

发表于 2022-09-04 19:57:22 回复(1)

提交观点

问题信息

字符串

难度：

74条回答 2431收藏 63269浏览

通过挑战的用户

查看代码

AHAHAHAHA6

2023-03-06 11:17:33
奈何笑不了

2023-03-02 16:44:55
牛客15248...

2023-01-25 02:03:36
思钱想厚008

2023-01-08 00:27:36
梧桐上的小鸟

2022-12-18 16:00:23

查找两个字符串a,b中的最长公共子串

输入描述:

输出描述:

输入

输出

说明

输入

输出

暴力破解竟然没超时

问题信息

热门推荐

通过挑战的用户

相关试题