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

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        if (str1.length() >= str2.length()) {
            helper(str2, str1);
            // doublePointer(str2, str1);
        } else {
            helper(str1,str2);
            // doublePointer(str1, str2);
        }
    }

    /**
     * 动态规划，dp[i][j]表示子串str1[1...i]中以i结尾的子串 和 子串str2[1...j]中以j结尾的子串 之间的最长公共子串
     * 当str1[i] == str2[j]时，dp[i][j] = dp[i-1][j-1]+1;
     * 否则，dp[i][j] = 0；
     * 注意：此题是最长公共子串，不是子序列
     */
    public static void helper(String str1, String str2) {
        // str1是短字符串，str2是长字符串
        int l1 = str1.length(), l2 = str2.length();
        int[][] dp = new int[l1+1][l2+1];
        int max = 0;  // 最长字串长度
        int index = 0;  // 生成最长子串时的短字符串子串的结尾位置
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        index = i;
                    }
                }
            }
        }
        System.out.println(str1.substring(index - max, index));
    }
    
    public static void doublePointer(String str1, String str2) {
        // str1是短字符串，str2是长字符串
        String result = "";
        int left = 0;  // 左指针
        int right = left + 1;  // 右指针
        while (right <= str1.length()) {
            String tmp = str1.substring(left, right);
            if (str2.contains(tmp)) {
                if (result.length() < tmp.length()) {
                    result = tmp;
                }
                right++;   // 是子串的情况下，只移动右指针
            } else {
                // 左指针移动一位
                left++;
                right = left + 1;
            }
        }
        System.out.println(result);
    }
}