我遇到了一个问题声明，找到了 给定两个子字符串之间 的 所有公共子字符串，因此 在每种情况下都必须打印最长的子字符串。问题陈述如下：

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

例如，给定输入字符串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从 ，因为这两个s的已经包含在上面提到的。但也不应该包括，，等，因为这些也都被覆盖。**e** atsleepnightxyz eatsl **e** epabcxyz``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

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 2 m）算法。
7. 整个算法所需的时间为
8. Tn =（S1中的子字符串数）*（字符比较过程的平均子字符串长度时间）
9. 通过执行某些计算，我得出的结论是时间复杂度为O（n 3 m 2）
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的情况下，输出应该是：neerajis和great ，但在S1和S3的情况下，输出应该是：
neerajis，raj，great，eat但还是我得到neerajis和great作为输出。我需要弄清楚这一点。

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