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

import java.util.Scanner;
//动态规划
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            if (s1.length() > s2.length()) { //让字符串较短的那个串为s1
                String temp = s1;
                s1 = s2;
                s2 = temp;
            }
            StringBuilder sb = new StringBuilder();
            int maxLen = 0;
            for (int i = 0 ; i < s1.length() ; ++i) {

                for (int j = 0 ; j < s2.length() ; ++j) {
                    int s1Pos = i;
                    int len = 0;
                    for (int k = j ; k < s2.length() ; ++k) {
                        if (s1Pos == s1.length() || s2.charAt(k) != s1.charAt(s1Pos)) {
                            break;
                        } else {
                            //System.out.println(s2.charAt(k) + " " + s1.charAt(s1Pos));
                            ++len;
                            ++s1Pos;
                        }
                    }
                    if (maxLen < len) {
                        maxLen = len;
                        sb = new StringBuilder(s1.substring(i, s1Pos));
                    }

                }
            }
            //System.out.println(sb.toString());
            System.out.println(dp(s1,s2));
        }
    }

    public static String dp(String s1, String s2) {
        if (s1.length() > s2.length()) {
            String temp = s1;
            s1 = s2;
            s2 = temp;
        }
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1]; //表示以字符串s1的i结尾和字符串s2的j结尾最大匹配字符个数

        int maxLen = 0;
        int end = 0;
        for (int i = 1 ; i <= m ; ++i) {
            for (int j = 1 ; j <= n ; ++j) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        end = i;
                        maxLen = dp[i][j];
                    }
                }

            }
        }
        return s1.substring(end - maxLen, end);
    }
}