import java.util.*;

public class Solution {

    /**

     * longest common substring

     * @param str1 string字符串 the string

     * @param str2 string字符串 the string

     * @return string字符串

     */

    public String LCS (String str1, String str2) {

        int len1 = str1.length(), len2 = str2.length();

        String[][] dp = new String[len1 + 1][len2 + 1]; //为何初始化为len+1，相当于从1-n

        int max = 0;

        String res = "";

        for(int i = 0; i <= len1; i++) {

            for(int j = 0; j <= len2; j++) {

                if(i == 0 || j == 0) {

                    dp[i][j] = "";

                } else if(str1.charAt(i - 1) == str2.charAt(j - 1)) {

                    dp[i][j] = dp[i - 1][j - 1] + str1.charAt(i - 1);

                    if(dp[i][j].length() > max) {

                        max = dp[i][j].length();

                        res = dp[i][j];

                    }

                } else {

                    dp[i][j] = "";

                }

            }

        }

        return res;

    }

}

public static String LCS (String str1, String str2) {

        int len1 = str1.length(), len2 = str2.length();

        int[][] dp = new int[len1 + 1][len2 + 1];

        int max = 0;

        int index  = 0;

        for(int i = 0; i < len1; i++) {

            for(int j = 0; j < len2; j++) {

                if(str1.charAt(i) == str2.charAt(j)) {

                    dp[i + 1][j + 1] = dp[i][j] + 1;

                }

                if(dp[i + 1][j + 1] > max) {

                    max = dp[i + 1][j + 1];

                    index = i;

                }

            }

        }

        return str1.substring(index - max + 1, index + 1);

    }