我正在尝试实现修改版本的最长公共子串算法,其中我不想将单词分开。
例如:
String s1 = "hi there how are you";
String s2 = "hi there how ar";
输出应该是:
hi there how
。我首先计算最长公共子串,然后过滤任何被分开的单词,以下是相应的代码:
private static void longestCommonSubstring(String S1, String S2) {
int Start = 0;
int Max = 0;
for (int i = 0; i < S1.length(); i++) {
for (int j = 0; j < S2.length(); j++) {
int x = 0;
while (S1.charAt(i + x) == S2.charAt(j + x)) {
x++;
if (((i + x) >= S1.length()) || ((j + x) >= S2.length()))
break;
}
if (x > Max) {
Max = x;
Start = i;
}
}
}
System.out.println("S1 " + S1 + " S2 " + S2 + " " + Start + " " + Max);
System.out.println("ans " + S1.substring(Start, (Start+Max)));
if(Start != 0){
if((S1.charAt(Start-1) == ' ')){
if(Start+Max != S1.length()){
if((S1.charAt(Start+Max) == ' ')){
System.out.println(S1.substring(Start, (Start + Max)));
}
}
}
else if((S1.charAt(Start+Max) == ' ')){
int index = S1.indexOf(' ', Start);
System.out.println(S1.substring(index+1, (Start + Max)));
}
else{
int index = S1.indexOf(' ', Start);
int lastIndex = S1.lastIndexOf(' ', (Start+Max));
if(index+1 != lastIndex+1){
System.out.println(S1.substring(index+1, lastIndex));
}
else{
System.out.println(" ");
}
}
}
else if(Start == 0 && Start+Max != S1.length() && (S1.charAt(Start+Max) == ' ')){
System.out.println(S1.substring(Start, (Start + Max)));
}
else if(Start+Max != S1.length()){
int index = S1.lastIndexOf(' ', (Start+Max));
System.out.println(S1.substring(Start, index));
}
else{
System.out.println(S1.substring(Start, (Start + Max)));
}
}
但是对于以下情况,它会失败:
String s1 = "hi there how are you";
String s2 = "i ere ho ar you";
输出应该是"you",但是却是空的,因为最长公共子串是"ere ho"。
感谢您的帮助。
charAt
。 - Murat Karagöz