题解 | #公共子串计算#

import java.util.Scanner;

// mark一下 经典
// 注意和题目：HJ65 《查找两个字符串a,b中的最长公共子串》https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?tpId=37&tqId=21288&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=undefined&tags=&title=

// 如果是最长公共 子序列
// a[i] != b[j] -> dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
// a[i] == b[j] -> dp[i][j] = dp[i - 1][j - 1] + 1

// 字串和子序列 i == 0 || j == 0 -> dp[i][j] = 0
// 方法1更容易理解和编写
// 方法一：短字符串头尾双指针判断是否包含与长字符串中
// 方法二：动态规划 dp[i][j] ：以a[i]和b[j]结尾的两个字符串的最长字串
// 递归方程：if (a[i] == b[j]) 则：dp[i][j] = dp[i - 1][j - 1] + 1
// 时刻更新最大值即可

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            if (s1.length() > s2.length()) {
                String tmp = s1;
                s1 = s2;
                s2 = tmp;
            }
            int ans = 0;
            int length = s1.length();
            for (int i = 0; i < length; i++) {
                for (int j = length; j > i; j--) {
                    String substr = s1.substring(i, j);
                    if (s2.contains(substr)) {
                        ans = Math.max(ans, j - i);
                        break;
                    }
                }
            }
            System.out.println(ans);
        }
    }
}


// 方法2
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            int length1 = s1.length();
            int length2 = s2.length();
            int[][] dp = new int[length1 + 1][length2 + 1];
            int ans = 0;
            // dp题目 数组大小初始化为长度 遍历从1开始 
            for (int i = 1; i <= length1; i++) {
                for (int j = 1; j <= length2; j++) {
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    ans = Math.max(ans, dp[i][j]);
                }
            }

            System.out.println(ans);
        }
    }
}