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

import java.util.Scanner;

/**
 * @author Dreams
 * @program Niuke
 * @description
 * @create 2021-09-16 09:23
 **/

public class Main {

    /**
     * abcdefghijklmnop
     * abcsafjklmnopqrstuvw
     * <p>
     * dp[i][j]：短字符串中的第i个字符，在长字符串中以其结尾的公共字符串最大长度
     * a b
     * a b c d e f j
     * a  b  d  c  d  a  e
     * a  1  0  0  0  0  0
     * b  0  2  0  0  0  0
     * c  0  0  0  3  0  0
     * e  0  0     0  0  0  1

     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            if (str1.length() > str2.length()) {
                String tmp = str1;
                str1 = str2;
                str2 = tmp;
            }

            int len1 = str1.length();
            int len2 = str2.length();
            char[] c1 = str1.toCharArray();
            char[] c2 = str2.toCharArray();

            int[][] dp = new int[len1][len2];
            for (int i = 0; i < len2; i++) {
                if (c1[0] == c2[i]) {
                dp[0][i] = 1;

                }
            }
            int maxI = 0;
            int maxj = 0;
            int max = 1;
            for (int i = 1; i < len1; i++) {
                for (int j = 1; j < len2; j++) {
                    if (c1[i] == c2[j]) {
                        dp[i][j] = Math.max(1, dp[i][j]);
                    }
                    if (c1[i] == c2[j] && c1[i - 1] == c2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }

                    if (max < dp[i][j]) {
                        max = dp[i][j];
                        maxI = i;
                    }

                }

            }

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

        }
    }
}