我遇到了一个问题，需要找到给定两个子字符串之间的所有公共子串，并且在每种情况下都要打印最长的子串。问题陈述如下：
编写一个程序来查找两个给定字符串之间的公共子字符串。但是，请勿包括包含在较长公共子字符串中的子字符串。
例如，给定输入字符串eatsleepnightxyz和eatsleepabcxyz，则结果应为：
- eatsleep（由于eatsleepnightxyz和eatsleepabcxyz中的eatsleep） - xyz（由于eatsleepnightxyz和eatsleepabcxyz中的xyz） - a（由于eatsleepnightxyz和eatsleepabcxyz中的a） - t（由于eatsleepnightxyz和eatsleepabcxyz中的t）
但是，结果集不应包括eatsleepnightxyz中的e或者eatsleepabxyz中的e，因为这两个e已经包含在上面提到的eatsleep中。也不应包括ea、eat、ats等，因为这些也都被eatsleep覆盖了。
在此过程中，您无需使用String实用程序方法，如contains、indexOf、StringTokenizer、split和replace。
我的算法如下：我从暴力算法开始，并将在提高基本理解后切换到更优化的解决方案。
尝试计算我的方法的时间复杂度。
让两个给定的字符串分别为n1-String和n2-String。
S1的子字符串数量显然是n1(n1+1)/2。
但我们需要找到S1子字符串的平均长度。
假设它是m。我们将单独找到m。
检查一个m-String是否是n-String的子字符串的时间复杂度是O(n*m)。
现在，我们正在检查每个m-String是否是n2-String中的子字符串。
这就是一个O(n^2 m)算法。
然后整个算法所需的时间为：
Tn=(S1中的子字符串数)*(平均子字符串长度*字符比较过程的时间)
通过进行某些计算，我得出结论时间复杂度是O(n^3 m^2)。
现在，我们的工作是以n1为单位找到m。
Tn = (n)(1) + (n-1)(2) + (n-2)(3) + ..... + (2)(n-1) + (1)(n)
其中Tn是所有子字符串长度的总和。
平均值将是此总和除以生成的子字符串的总数。
这只是一个求和和除法问题，其解决方案如下O(n)。
因此...
我的算法的运行时间为O(n^5)。
有了这个想法，我编写了以下代码：
问题：给定以下输入
如果是S1和S2，输出应该是：
如何设计我的代码？
编写一个程序来查找两个给定字符串之间的公共子字符串。但是，请勿包括包含在较长公共子字符串中的子字符串。
例如，给定输入字符串eatsleepnightxyz和eatsleepabcxyz，则结果应为：
- eatsleep（由于eatsleepnightxyz和eatsleepabcxyz中的eatsleep） - xyz（由于eatsleepnightxyz和eatsleepabcxyz中的xyz） - a（由于eatsleepnightxyz和eatsleepabcxyz中的a） - t（由于eatsleepnightxyz和eatsleepabcxyz中的t）
但是，结果集不应包括eatsleepnightxyz中的e或者eatsleepabxyz中的e，因为这两个e已经包含在上面提到的eatsleep中。也不应包括ea、eat、ats等，因为这些也都被eatsleep覆盖了。
在此过程中，您无需使用String实用程序方法，如contains、indexOf、StringTokenizer、split和replace。
我的算法如下：我从暴力算法开始，并将在提高基本理解后切换到更优化的解决方案。
For String S1:
Find all the substrings of S1 of all the lengths
While doing so: Check if it is also a substring of
S2.
尝试计算我的方法的时间复杂度。
让两个给定的字符串分别为n1-String和n2-String。
S1的子字符串数量显然是n1(n1+1)/2。
但我们需要找到S1子字符串的平均长度。
假设它是m。我们将单独找到m。
检查一个m-String是否是n-String的子字符串的时间复杂度是O(n*m)。
现在，我们正在检查每个m-String是否是n2-String中的子字符串。
这就是一个O(n^2 m)算法。
然后整个算法所需的时间为：
Tn=(S1中的子字符串数)*(平均子字符串长度*字符比较过程的时间)
通过进行某些计算，我得出结论时间复杂度是O(n^3 m^2)。
现在，我们的工作是以n1为单位找到m。
Tn = (n)(1) + (n-1)(2) + (n-2)(3) + ..... + (2)(n-1) + (1)(n)
其中Tn是所有子字符串长度的总和。
平均值将是此总和除以生成的子字符串的总数。
这只是一个求和和除法问题，其解决方案如下O(n)。
因此...
我的算法的运行时间为O(n^5)。
有了这个想法，我编写了以下代码：
package pack.common.substrings;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
public class FindCommon2 {
public static final Set<String> commonSubstrings = new LinkedHashSet<String>();
public static void main(String[] args) {
printCommonSubstrings("neerajisgreat", "neerajisnotgreat");
System.out.println(commonSubstrings);
}
public static void printCommonSubstrings(String s1, String s2) {
for (int i = 0; i < s1.length();) {
List<String> list = new ArrayList<String>();
for (int j = i; j < s1.length(); j++) {
String subStr = s1.substring(i, j + 1);
if (isSubstring(subStr, s2)) {
list.add(subStr);
}
}
if (!list.isEmpty()) {
String s = list.get(list.size() - 1);
commonSubstrings.add(s);
i += s.length();
}
}
}
public static boolean isSubstring(String s1, String s2) {
boolean isSubstring = true;
int strLen = s2.length();
int strToCheckLen = s1.length();
if (strToCheckLen > strLen) {
isSubstring = false;
} else {
for (int i = 0; i <= (strLen - strToCheckLen); i++) {
int index = i;
int startingIndex = i;
for (int j = 0; j < strToCheckLen; j++) {
if (!(s1.charAt(j) == s2.charAt(index))) {
break;
} else {
index++;
}
}
if ((index - startingIndex) < strToCheckLen) {
isSubstring = false;
} else {
isSubstring = true;
break;
}
}
}
return isSubstring;
}
}
我的代码解释：
printCommonSubstrings: Finds all the substrings of S1 and
checks if it is also a substring of
S2.
isSubstring : As the name suggests, it checks if the given string
is a substring of the other string.
问题：给定以下输入
S1 = “neerajisgreat”;
S2 = “neerajisnotgreat”
S3 = “rajeatneerajisnotgreat”
如果是S1和S2，输出应该是：
neerajis和great。但如果是S1和S3，则输出应为：neerajis、raj、great和eat，但实际上我仍然得到的是neerajis和great，我需要找出问题所在。如何设计我的代码？