algorithm - 具有重叠的字符串连接的高效算法

Question

我们需要通过连接将数据库中的 3 列组合起来。但是，这 3 列可能包含重叠部分，并且这些部分不应重复。例如，

  "a" + "b" + "c" => "abc"
  "abcde" + "defgh" + "ghlmn" => "abcdefghlmn"
  "abcdede" + "dedefgh" + "" => "abcdedefgh"
  "abcde" + "d" + "ghlmn" => "abcdedghlmn"
  "abcdef" + "" + "defghl" => "abcdefghl"

我们当前的算法非常慢，因为它使用蛮力来识别 2 个字符串之间的重叠部分。有谁知道执行此操作的有效算法吗？

假设我们有 2 个字符串 A 和 B。算法需要找到最长的公共(public)子串 S，使得 A 以 S 结尾，B 以 S 开头。

附上我们当前在 Java 中的暴力实现以供引用，

public static String concat(String s1, String s2) {
    if (s1 == null)
        return s2;
    if (s2 == null)
        return s1;
    int len = Math.min(s1.length(), s2.length());

    // Find the index for the end of overlapping part
    int index = -1;
    for (int i = len; i > 0; i--) {
        String substring = s2.substring(0, i);
        if (s1.endsWith(substring)) {
            index = i;
            break;
        }
    }
    StringBuilder sb = new StringBuilder(s1);
    if (index < 0) 
        sb.append(s2);
    else if (index <= s2.length())
        sb.append(s2.substring(index));
    return sb.toString();
}

Answer 1

大多数其他答案都集中在常数因子优化上，但也可以渐进地做得更好。看看你的算法:它是 O(N^2)。这似乎是一个可以比那更快解决的问题!

考虑 Knuth Morris Pratt .它跟踪到目前为止我们匹配的最大子串数量。这意味着它知道 在 S2 的末尾匹配了多少 S1，这就是我们要寻找的值!只需修改算法以在早期匹配子字符串时继续而不是返回，并让它在末尾返回匹配的数量而不是 0。

这为您提供了一个 O(n) 算法。不错!

    int OverlappedStringLength(string s1, string s2) {
        //Trim s1 so it isn't longer than s2
        if (s1.Length > s2.Length) s1 = s1.Substring(s1.Length - s2.Length);

        int[] T = ComputeBackTrackTable(s2); //O(n)

        int m = 0;
        int i = 0;
        while (m + i < s1.Length) {
            if (s2[i] == s1[m + i]) {
                i += 1;
                //<-- removed the return case here, because |s1| <= |s2|
            } else {
                m += i - T[i];
                if (i > 0) i = T[i];
            }
        }

        return i; //<-- changed the return here to return characters matched
    }

    int[] ComputeBackTrackTable(string s) {
        var T = new int[s.Length];
        int cnd = 0;
        T[0] = -1;
        T[1] = 0;
        int pos = 2;
        while (pos < s.Length) {
            if (s[pos - 1] == s[cnd]) {
                T[pos] = cnd + 1;
                pos += 1;
                cnd += 1;
            } else if (cnd > 0) {
                cnd = T[cnd];
            } else {
                T[pos] = 0;
                pos += 1;
            }
        }

        return T;
    }

OverlappedStringLength("abcdef", "defghl") 返回 3