题解 | #公共子串计算#

方法一：循环遍历

方法二：动态规划

方法三：由于dp[i][j]在迭代时只与dp[i-1][j-1]有关,可在方法二的基础上对dp数组进行空间优化，用2xN的数组代替NxN的数组

import java.util.Scanner;

//3.动态规划-空间优化版
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int[][] dp = new int[2][s2.length() + 1];
        int max = 0;
        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[1][j] = dp[0][j - 1] + 1;
                } else {
                    dp[1][j] = 0;
                }
                max = Math.max(max, dp[1][j]);
            }
            for (int j = 1 ; j <= s2.length(); j++) {
                dp[0][j] = dp[1][j];
            }
        }
        System.out.print(max);
    }
}

// //2.动态规划
// public class Main {
//     public static void main(String[] args) {
//         Scanner sc = new Scanner(System.in);
//         String s1 = sc.nextLine();
//         String s2 = sc.nextLine();
//         int[][] dp = new int[s1.length() + 1][s2.length() + 1];
//         int max = 0;
//         for (int i = 0 ; i <= s1.length(); i++) {
//             for (int j = 0 ; j <= s2.length(); j++) {
//                 if (i == 0 || j == 0) {
//                     dp[i][j] = 0;
//                 } else {
//                     if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
//                         dp[i][j] = dp[i - 1][j - 1] + 1;
//                     } else {
//                         dp[i][j] = 0;
//                     }
//                 }
//                 max = Math.max(max, dp[i][j]);
//             }
//         }
//         System.out.print(max);
//     }
// }

// //1.循环遍历
// public class Main {
//     public static void main(String[] args) {
//         Scanner sc = new Scanner(System.in);
//         String s1 = sc.nextLine();
//         String s2 = sc.nextLine();
//         if (s1.length() > s2.length()) {
//             String temp = s1;
//             s1 = s2;
//             s2 = temp;
//         }
//         int n = s1.length() + 1;
//         String resStr = "";
//         boolean flag = false;
//         while (!flag && --n > 0) {
//             for (int i = 0 ; i <= s1.length() - n; i++) {
//                 String str = s1.substring(i, i + n);
//                 if (s2.contains(str)) {
//                     resStr = str;
//                     flag = true;
//                 }
//             }
//         }
//         System.out.print(n);
//     }
// }