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

用动态规划寻找最长公共子串的方法，找到最长公共子串，然后找到这个最长公共子串的在较短字符串中的位置

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);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            new Main().maxsharezichuan(a, b);
        }
    }
    void maxsharezichuan(String s1, String s2) {
        int tsr = 0;
        int tsc = 0;
	  //区分出长串和短串，使短串为动态规划表的行，长串为列
        String minstr = "";
        String maxstr = "";
        if (s1.length() < s2.length()) {
            tsr = s1.length() + 1;
            tsc = s2.length() + 1;
            minstr = s1;
            maxstr = s2;
        } else {
            tsr = s2.length() + 1;
            tsc = s1.length() + 1;
            minstr = s2;
            maxstr = s1;
        }
        String out = "";
        int[][] ts = new int[tsr][tsc];
        for (int c = 0; c < tsc; c++) {
            ts[0][c] = 0;
        }
        for (int c = 0; c < tsr; c++) {
            ts[c][0] = 0;
        }
        for (int i = 1; i < tsr; i++) {
            char s1c = minstr.charAt(i - 1);
            for (int j = 1; j < tsc; j++) {
                char s2c = maxstr.charAt(j - 1);
			  //动态规划方法寻找最长公公共子串的公式。
                if (s1c == s2c) {
                    ts[i][j] = 1 + ts[i - 1][j - 1];
                } else {
                    ts[i][j] = 0;
                }
            }
        }
	  //找到表中最大的那个值（这个值在表中不一定是足后一个位置，所以要遍历寻找，也可以在填表时直接找），即为最长公共子串的长度
        int maxrow = 0;
        for (int f = 0; f < tsr; f++) {
            maxrow = Math.max(Arrays.stream(ts[f]).max().getAsInt(), maxrow);
        }
	  //再次遍历，找到这个最大值第一次出现的行，那么行值-1即为最长公共子串结束的位置
        int maxi = 0;
        int maxj = 0;
        for (int i = 0; i < ts.length; i++) {
            for (int j = 0; j < ts[i].length; j++) {
                if (ts[i][j] == maxrow) {
                    maxi = i;
                    maxj = j;
                    break;
                }
            }
            if (maxi > 0 || maxj > 0) {
                break;
            }
        }
	  //根据位置及长度，截取最长公共子串输出
        out = minstr.substring(maxi - maxrow, maxi);
        System.out.println(out);
    }
}