java - 查找给定两个字符串的所有公共(public)子字符串

Question

我遇到了一个问题语句来查找 给定两个子字符串之间的所有公共(public)子字符串，这样在每种情况下您都必须打印最长的子字符串。问题陈述如下:

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.

For example, given the input strings eatsleepnightxyz and eatsleepabcxyz, the results should be:

• eatsleep (due to <b>eatsleep</b>nightxyz <b>eatsleep</b>abcxyz)
• xyz (due to eatsleepnight<b>xyz</b> eatsleepabc<b>xyz</b>)
• a (due to e<b>a</b>tsleepnightxyz eatsleep<b>a</b>bcxyz)
• t (due to eatsleepnigh<b>t</b>xyz ea<b>t</b>sleepabcxyz)

However, the result set should not include e from <b>e</b>atsleepnightxyz eatsl<b>e</b>epabcxyz, 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.

In this, you don't have to make use of String utility methods like: 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-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 字符串。
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 的情况下，输出应为:neerajis和 great但在 S1 和 S3 的情况下，输出应该是: neerajis , raj , great , eat但我仍然得到neerajis和 great作为输出。我需要弄清楚这一点。

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

Answer 1

使用适合任务的算法而不是蛮力方法会更好。维基百科描述了 longest common substring problem 的两种常见解决方案:suffix-tree 和 dynamic-programming。

动态规划解决方案需要 O(n m) 时间和 O(n m) 空间。这几乎是对最长公共(public)子字符串的 Wikipedia 伪代码的直接 Java 翻译:

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;
}

现在，您需要所有公共(public)子字符串，而不仅仅是最长的。您可以增强此算法以包含更短的结果。让我们检查示例输入 eatsleepnightxyz 和 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 表示。

左侧、顶部和 6 和 7 旁边的其他 1 呢？这些不算在内，因为它们出现在由 12345678 对角线形成的矩形内——换句话说，它们已经被 eatsleep 覆盖了。

我建议只做一次，只做一张 table 。然后，进行第二次遍历，从右下角向后迭代，以收集结果集。