题解 | #公共子串计算#动态规划+暴力

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // System.out.println(bruteForce(in.nextLine(), in.nextLine()));
        System.out.println(dp(in.nextLine(), in.nextLine()));
    }

    // 先找出所有的公共子串，不论长短
    static int dp(String s1, String s2) {
        String[][] d = new String[s1.length()][s2.length()];
        int maxLen = 0;
        for (int i = 0; i < s1.length() ; i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    if (i - 1 < 0 || j - 1 < 0) {
                        d[i][j] = String.valueOf(s1.charAt(i));
                    } else {
                        d[i][j] = d[i - 1][j - 1] + String.valueOf(s1.charAt(i));
                    }
                } else {
                    d[i][j] = String.valueOf("");
                }
                maxLen = Math.max(maxLen, d[i][j].length());
            }
        }
        return maxLen;
    }

    // 暴力 找出所有子串，然后比较
    static int bruteForce(String s1, String s2) {
        int len = s1.length();
        while (len > 0) {
            for (int i = 0; i + len - 1 < s1.length(); i++) {
                String sub = s1.substring(i, i + len);
                if (s2.contains(sub)) {
                    return len;
                }
            }
            len--;
        }
        return 0;
    }
}