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

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 a = in.nextLine();
            String b = in.nextLine();
            String longStr = a.length()>b.length()?a:b;
            String shortStr = a.length()>b.length()?b:a;
            int maxLen = 0;
            String commonStr = "";
            for(int len = shortStr.length() - 1;len>=0;len--){               
                for(int i=0;i<shortStr.length() - len;i++){
                    if(longStr.contains(shortStr.substring(i,i+len)) && len > maxLen){
                        maxLen = len;
                        commonStr = shortStr.substring(i,i+len);
                        break;
                    }
                }
            }
            System.out.print(commonStr);
        }
    }
}

一道经典的子序列系列动态规划题目,dp[i][j]含义为以i - 1为结尾的s和j - 1结尾的t的最长公共子串长度
（这里要求连续，所以当遍历的s、t字符不相等时，递推公式不应该为dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])），而是忽略它（即dp[i][j] = 0）。
而当两字符相等时，dp[i][j] = dp[i - 1][j - 1] + 1,随时存储最大值max，并记录此时的左右边界，便于切割字符串返回结果。
这里有点不同的是题目要求输出较短串的最先出现的最长公共子串，所以开始遍历之前，要确保外层循环为较短的子串。
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String t = in.nextLine();
            if (s.length() > t.length()) {
                String temp = s;
                s = t;
                t = temp;
            }
            int[][] dp = new int[s.length() + 1][t.length() + 1];
            int max = 0, resLeft = 0, resRight = 0;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= t.length(); j++) {
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        if (dp[i][j] > max) {
                            resLeft = i - dp[i][j];
                            resRight = i - 1;
                            max = dp[i][j];
                        }
                    }
                }
            }
            System.out.println(s.substring(resLeft, resRight + 1));
        }
    }
}

暴力破解竟然没超时

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; // 直接返回
                }
            }
        }
    }
}

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));
        }
    }
}

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]));
        }
    }
}

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;
                }
            }
        }
    }
}

写段垃圾代码

时间复杂度

空间复杂度

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 ));
    }
}

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);
    }
}

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

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;
    }