我遇到了一个问题陈述,找到给定的两个子字符串之间的所有公共子字符串,这样在每种情况下都必须打印最长的子字符串。问题陈述如下:
I have come across a problem statement to find the all the common sub-strings between the given two sub-strings such a way that in every case you have to print the longest sub-string. The problem statement is as follows:
编写程序以查找两个给定字符串之间的公共子字符串。但是,不要包含较长公共子字符串中包含的子字符串。
Write a program to find the common substrings between the two given strings. However, do not include substrings that are contained within longer common substrings.
例如,给定输入字符串 eatsleepnightxyz 和 eatsleepabcxyz ,结果应为:
For example, given the input strings eatsleepnightxyz and eatsleepabcxyz, the results should be:
- eatsleep (由于 eatsleep nightxyz eatsleep abcxyz )
- xyz (由于 eatsleepnight xyz eatsleepabc xyz )
- a (由于 e a tsleepnightxyz eatsleep a bcxyz )
- t (由于 eatsleepnigh t xyz ea t sleepabcxyz )
- eatsleep (due to eatsleepnightxyz eatsleepabcxyz)
- xyz (due to eatsleepnightxyz eatsleepabcxyz)
- a (due to eatsleepnightxyz eatsleepabcxyz)
- t (due to eatsleepnightxyz eatsleepabcxyz)
但是,结果集不包括 e 来自 e atsleepnightxyz eatsl e epabcxyz ,因为 e 已经是包含在上面提到的 eatsleep 中。你也不应该包括 ea ,吃, ats 等等。,因为这些也都被 eatsleep 所涵盖。
However, the result set should not include e from eatsleepnightxyz eatsleepabcxyz, because both es are already contained in the eatsleep mentioned above. Nor should you include ea, eat, ats, etc., as those are also all covered by eatsleep.
在此,你不必使用String实用程序方法如:contains,indexOf,StringTokenizer,split和replace。
In this, you don't have to make use of String utility methods like: contains, indexOf, StringTokenizer, split and replace.
我的算法如下:我从粗暴开始当我提高基本理解时,强制并将切换到更优化的解决方案。
My Algorithm is as follows: I am starting with brute force and will switch to more optimized solution when I improve my basic understanding.
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.尝试弄清楚我的方法的时间复杂性。
Attempt to figure out the time complexity of my approach.
让两个给定的字符串为n1-String和n2-String
尝试用n1来找到m。
T n =(n)(1)+(n-1)(2)+(n-2)(3)+。 .... +(2)(n-1)+(1)(n) 其中T n 是所有子串的长度之和。
Tn = (n)(1) + (n-1)(2) + (n-2)(3) + ..... + (2)(n-1) + (1)(n) where Tn is the sum of lengths of all the substrings.
平均值是该总和除以生成的子串总数。
Average will be the division of this sum by the total number of Substrings produced.
这只是一个总和,划分问题,其解决方案如下:O(n)
This, simply is a summation and division problem whose solution is as follows O(n)
因此......
算法的运行时间为O(n ^ 5)。
Running time of my algorithm is O(n^5).
考虑到这一点,我编写了以下代码:
With this in mind I wrote the following code:
package packmon.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 和很好 但是在S1和S3的情况下,输出应该是: neerajis , raj ,很棒,吃但我仍然得到 neerajis 和很棒作为输出。我需要弄清楚这一点。
In case of S1 and S2, the output should be: neerajis and great but in case of S1 and S3, the output should have been: neerajis, raj, great, eat but still I am getting neerajis and great as output. I need to figure this out.
我应该如何设计我的代码?
How should I design my code?
推荐答案使用适当的算法算法而不是蛮力方法会更好。维基百科描述了最常见的子字符串问题的两种常见解决方案:后缀树和动态编程。
You would be better off with a proper algorithm for the task rather than a brute-force approach. Wikipedia describes two common solutions to the longest common substring problem: suffix-tree and dynamic-programming.
动态编程解决方案需要O( nm )时间和O( nm )空间。对于最长的公共子字符串,这几乎是对Wikipedia伪代码的直接Java翻译:
The dynamic programming solution takes O(n m) time and O(n m) space. This is pretty much a straightforward Java translation of the Wikipedia pseudocode for the longest common substring:
public static Set<String> longestCommonSubstrings(String s, String t) { int[][] table = new int[s.length()][t.length()]; int longest = 0; Set<String> result = new HashSet<>(); for (int i = 0; i < s.length(); i++) { for (int j = 0; j < t.length(); j++) { if (s.charAt(i) != t.charAt(j)) { continue; } table[i][j] = (i == 0 || j == 0) ? 1 : 1 + table[i - 1][j - 1]; if (table[i][j] > longest) { longest = table[i][j]; result.clear(); } if (table[i][j] == longest) { result.add(s.substring(i - longest + 1, i + 1)); } } } return result; }现在,您需要所有常见的子串,而不仅仅是最长的子串。您可以增强此算法以包含更短的结果。让我们检查表格中的示例输入 eatsleepnightxyz 和 eatsleepabcxyz :
Now, you want all of the common substrings, not just the longest. You can enhance this algorithm to include shorter results. Let's examine the table for the example inputs eatsleepnightxyz and eatsleepabcxyz:
e a t s l e e p a b c x y z e 1 0 0 0 0 1 1 0 0 0 0 0 0 0 a 0 2 0 0 0 0 0 0 1 0 0 0 0 0 t 0 0 3 0 0 0 0 0 0 0 0 0 0 0 s 0 0 0 4 0 0 0 0 0 0 0 0 0 0 l 0 0 0 0 5 0 0 0 0 0 0 0 0 0 e 1 0 0 0 0 6 1 0 0 0 0 0 0 0 e 1 0 0 0 0 1 7 0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 8 0 0 0 0 0 0 n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 0 0 0 0 g 0 0 0 0 0 0 0 0 0 0 0 0 0 0 h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 t 0 0 1 0 0 0 0 0 0 0 0 0 0 0 x 0 0 0 0 0 0 0 0 0 0 0 1 0 0 y 0 0 0 0 0 0 0 0 0 0 0 0 2 0 z 0 0 0 0 0 0 0 0 0 0 0 0 0 3
- eatsleep 结果很明显:这是左上角的 12345678 对角条纹。
- xyz 结果是右下角的 123 对角线。
- a 结果由顶部附近的 1 表示(第二行,第九列)。
- t 结果由左下角附近的 1 表示。
- The eatsleep result is obvious: that's the 12345678 diagonal streak at the top-left.
- The xyz result is the 123 diagonal at the bottom-right.
- The a result is indicated by the 1 near the top (second row, ninth column).
- The t result is indicated by the 1 near the bottom left.
左边,顶部和<$ c旁边的其他 1 怎么样? $ c> 6 和 7 ?那些不计算,因为它们出现在由 12345678 对角线形成的矩形内 - 换句话说,它们已被 eatsleep 。
What about the other 1s at the left, the top, and next to the 6 and 7? Those don't count because they appear within the rectangle formed by the 12345678 diagonal — in other words, they are already covered by eatsleep.
我建议除了构建表之外什么都不做。然后,进行第二次传递,从右下角向后迭代,以收集结果集。
I recommend doing one pass doing nothing but building the table. Then, make a second pass, iterating backwards from the bottom-right, to gather the result set.
更多推荐
查找给定两个字符串的所有常见子字符串
发布评论