我遇到了一个问题,需要找到给定两个子字符串之间的所有公共子串,并且在每种情况下都要打印最长的子串。问题陈述如下:
编写一个程序来查找两个给定字符串之间的公共子字符串。但是,请勿包括包含在较长公共子字符串中的子字符串。
例如,给定输入字符串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
,我需要找出问题所在。如何设计我的代码?