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();
}
// 找到两个字符串的最长公共子串
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=