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

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

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

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

• eatsleep（由于eatsleepnightxyz eatsleepabcxyz)
• xyz（由于eatsleepnightxyz eatsleepabcxyz)
• a（由于eatsleepnightxyz eatsleepabcxyz)
• t（由于eatsleepnightxyz eatsleepabcxyz)

但是，结果集不应包含 from ，因为上述两个 s 都已包含在中。也不应包含 、 、 等，因为这些也都包含在 .eeatsleepnightxyzeatsleepabcxyzeeatsleepeaeatatseatsleep

在这里，您不必使用String实用程序方法，例如：contains，indexOf，StringTokenizer，split and 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-字符串和 n2-字符串

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

尝试根据 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<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 的情况下，输出应该是：，但在 S1 和 S3 的情况下，输出应该是：、 、 、 ，但我仍然得到并作为输出。我需要弄清楚这一点。neerajisgreatneerajisrajgreateatneerajisgreat

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