import java.util.Scanner;
 
public class Main
 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        // 提示用户输入两个字符串
        System.out.print("请输入第一个字符串: ");
        String str1 = scanner.nextLine();
 
        System.out.print("请输入第二个字符串: ");
        String str2 = scanner.nextLine();
 
        // 调用findLongestCommonSubstring方法找到最长公共子串
        String longestCommonSubstring = findLongestCommonSubstring(str1, str2);
 
        // 输出最长公共子串
        System.out.println("最长公共子串为: " + longestCommonSubstring);
 
        scanner.close();
    }
 
    // 找到两个字符串的最长公共子串
    public static String findLongestCommonSubstring(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int maxLength = 0;
        int endIndex = 0;
 
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
 
        return str1.substring(endIndex - maxLength, endIndex);
    }
}
 

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKcHVibGljIGNsYXNzIE1haW4KIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTY2FubmVyIHNjYW5uZXIgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwogICAgICAgIAogICAgICAgIC8vIOaPkOekuueUqOaIt+i+k+WFpeS4pOS4quWtl+espuS4sgogICAgICAgIFN5c3RlbS5vdXQucHJpbnQoIuivt+i+k+WFpeesrOS4gOS4quWtl+espuS4sjogIik7CiAgICAgICAgU3RyaW5nIHN0cjEgPSBzY2FubmVyLm5leHRMaW5lKCk7CiAgICAgICAgCiAgICAgICAgU3lzdGVtLm91dC5wcmludCgi6K+36L6T5YWl56ys5LqM5Liq5a2X56ym5LiyOiAiKTsKICAgICAgICBTdHJpbmcgc3RyMiA9IHNjYW5uZXIubmV4dExpbmUoKTsKICAgICAgICAKICAgICAgICAvLyDosIPnlKhmaW5kTG9uZ2VzdENvbW1vblN1YnN0cmluZ+aWueazleaJvuWIsOacgOmVv+WFrOWFseWtkOS4sgogICAgICAgIFN0cmluZyBsb25nZXN0Q29tbW9uU3Vic3RyaW5nID0gZmluZExvbmdlc3RDb21tb25TdWJzdHJpbmcoc3RyMSwgc3RyMik7CiAgICAgICAgCiAgICAgICAgLy8g6L6T5Ye65pyA6ZW/5YWs5YWx5a2Q5LiyCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCLmnIDplb/lhazlhbHlrZDkuLLkuLo6ICIgKyBsb25nZXN0Q29tbW9uU3Vic3RyaW5nKTsKICAgICAgICAKICAgICAgICBzY2FubmVyLmNsb3NlKCk7CiAgICB9CiAgICAKICAgIC8vIOaJvuWIsOS4pOS4quWtl+espuS4sueahOacgOmVv+WFrOWFseWtkOS4sgogICAgcHVibGljIHN0YXRpYyBTdHJpbmcgZmluZExvbmdlc3RDb21tb25TdWJzdHJpbmcoU3RyaW5nIHN0cjEsIFN0cmluZyBzdHIyKSB7CiAgICAgICAgaW50W11bXSBkcCA9IG5ldyBpbnRbc3RyMS5sZW5ndGgoKSArIDFdW3N0cjIubGVuZ3RoKCkgKyAxXTsKICAgICAgICBpbnQgbWF4TGVuZ3RoID0gMDsKICAgICAgICBpbnQgZW5kSW5kZXggPSAwOwogICAgICAgIAogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IHN0cjEubGVuZ3RoKCk7IGkrKykgewogICAgICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBzdHIyLmxlbmd0aCgpOyBqKyspIHsKICAgICAgICAgICAgICAgIGlmIChzdHIxLmNoYXJBdChpIC0gMSkgPT0gc3RyMi5jaGFyQXQoaiAtIDEpKSB7CiAgICAgICAgICAgICAgICAgICAgZHBbaV1bal0gPSBkcFtpIC0gMV1baiAtIDFdICsgMTsKICAgICAgICAgICAgICAgICAgICBpZiAoZHBbaV1bal0gPiBtYXhMZW5ndGgpIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWF4TGVuZ3RoID0gZHBbaV1bal07CiAgICAgICAgICAgICAgICAgICAgICAgIGVuZEluZGV4ID0gaTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIGRwW2ldW2pdID0gMDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICByZXR1cm4gc3RyMS5zdWJzdHJpbmcoZW5kSW5kZXggLSBtYXhMZW5ndGgsIGVuZEluZGV4KTsKICAgIH0KfQo=

cXdlcnQKd2VyeXVpdWhuamk=

qwert
weryuiuhnji