查找给定两个字符串的所有常见子字符串

我遇到了一个问题陈述，找到给定的两个子字符串之间的所有常见子字符串，这样在每种情况下你都必须打印最长的子字符串。 问题陈述如下：

编写程序以查找两个给定字符串之间的公共子字符串。 但是，不要包含较长公共子字符串中包含的子字符串。

例如，给定输入字符串eatsleepnightxyz和eatsleepabcxyz ，结果应为：

• eatsleep （由于eatsleep nightxyz eatsleep abcxyz ）
• xyz （由于eatsleepnight xyz eatsleepabc xyz ）
• a （由于e a tsleepnightxyz eatsleep a bcxyz ）
• t （由于eatsleepnigh t xyz ea t sleepabcxyz ）

但是，结果集不应包括e e atsleepnightxyz eatsl e epabcxyz ，因为两者都已包含在上述的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

1. S1的子串数明显为n1（n1 + 1）/ 2。
2. 但我们必须找到S1的子串的平均长度。
3. 让我们说它是m。 我们将分别找到m。
4. 时间复杂度检查m-String是否是n-String的子串是O（n * m）。
5. 现在，我们正在检查每个m-String是S2的子串，它是一个n2-String。
6. 如上所述，这是一种O（n ² m）算法。
7. 那么整个算法所需的时间是
8. Tn =（S1中的子串数）*（字符比较过程的平均子串长度时间）
9. 通过执行某些计算，我得出结论，时间复杂度为O（n ³ m ² ）
10. 现在，我们的工作是找到m的n1。

尝试根据n1找到m。

T _n =（n）（1）+（n-1）（2）+（n-2）（3）+ ….. +（2）（n-1）+（1）（n）
其中T _n是所有子串的长度之和。

平均值是该总和除以生成的子串总数。

这只是一个求和和除法问题，其解决方案如下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 commonSubstrings = new LinkedHashSet(); 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 list = new ArrayList(); for (int j = i; j  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的输出。 我需要弄清楚这一点。

我应该如何设计我的代码？

Answer 1

使用适当的算法算法而不是蛮力方法会更好。 维基百科描述了最常见的子串问题的两种常见解决方案： 后缀树和动态编程 。

动态编程解决方案需要O（ nm ）时间和O（ nm ）空间。 对于最长的公共子字符串，这几乎是对Wikipedia伪代码的直接Java翻译：

 public static Set longestCommonSubstrings(String s, String t) { int[][] table = new int[s.length()][t.length()]; int longest = 0; Set 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 ：

  eatsleepabcxyz 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结果很明显：这是eatsleep的12345678对角条纹。
• xyz结果是右下角的123对角线。
• 结果由顶部附近的1 （第二行，第九列）表示。
• t结果由左下角附近的1表示。

左边，顶部和6和7旁边的其他1秒怎么样？ 那些不计算因为它们出现在由12345678对角线形成的矩形内 – 换句话说，它们已被eatsleep覆盖。

我建议做一个通行证，除了建立表格。 然后，进行第二次传递，从右下角向后迭代，以收集结果集。

Answer 2

通常，这种类型的子串匹配是在称为Trie （发音为try）的单独数据结构的帮助下完成的。 最适合此问题的特定变体是后缀树 。 您的第一步应该是接受输入并构建后缀树。 然后你需要使用后缀树来确定最长的公共子串，这是一个很好的练习。