代码之家 › 专栏 › 技术社区 › ZZ Coder

带重叠的字符串连接的高效算法

string language-agnostic algorithm

ZZ Coder · 技术社区 · 15 年前

我们需要通过连接在数据库中组合3列。但是,3列可能包含重叠部分,不应重复这些部分。例如,

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

我们当前的算法非常慢,因为它使用蛮力来识别两个字符串之间的重叠部分。有人知道一种有效的算法吗?

假设我们有2个字符串a和b,算法需要找到最长的公共子字符串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();
}

12 回复 | 直到 8 年前

Craig Gidney Mihai 9 年前

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

考虑 Knuth Morris Pratt . 它跟踪我们迄今为止匹配的最大子字符串数量。这意味着它知道s1中有多少是匹配的 在s2末尾 这就是我们要寻找的价值!只需修改算法以继续,而不是在早期匹配子字符串时返回,并让它返回匹配的金额而不是末尾的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

Daniel C. Sobral 15 年前

您可以使用DFA。例如,字符串 XYZ 应该由正则表达式读取 ^((A)?B)?C . 该正则表达式将匹配与 XYZ 字符串。使用这样的正则表达式,您可以匹配并获得匹配结果,或者生成一个DFA,在该DFA上,您可以使用状态来指示“剪切”的正确位置。

在scala中,第一个实现(直接使用regex)可能如下所示:

def toRegex(s1: String) = "^" + s1.map(_.toString).reduceLeft((a, b) => "("+a+")?"+b) r
def concatWithoutMatch(s1 : String, s2: String) = {
  val regex = toRegex(s1)
  val prefix = regex findFirstIn s2 getOrElse ""
  s1 + s2.drop(prefix length)
}

例如:

scala> concatWithoutMatch("abXabXabXac", "XabXacd")
res9: java.lang.String = abXabXabXacd

scala> concatWithoutMatch("abc", "def")
res10: java.lang.String = abcdef

scala> concatWithoutMatch(concatWithoutMatch("abcde", "defgh"), "ghlmn")
res11: java.lang.String = abcdefghlmn

jerryjvl 15 年前

你觉得怎么样(请原谅C):

public static string OverlapConcat(string s1, string s2)
{
    // Handle nulls... never return a null
    if (string.IsNullOrEmpty(s1))
    {
        if (string.IsNullOrEmpty(s2))
            return string.Empty;
        else
            return s2;
    }
    if (string.IsNullOrEmpty(s2))
        return s1;

    // Checks above guarantee both strings have at least one character
    int len1 = s1.Length - 1;
    char last1 = s1[len1];
    char first2 = s2[0];

    // Find the first potential match, bounded by the length of s1
    int indexOfLast2 = s2.LastIndexOf(last1, Math.Min(len1, s2.Length - 1));
    while (indexOfLast2 != -1)
    {
        if (s1[len1 - indexOfLast2] == first2)
        {
            // After the quick check, do a full check
            int ix = indexOfLast2;
            while ((ix != -1) && (s1[len1 - indexOfLast2 + ix] == s2[ix]))
                ix--;
            if (ix == -1)
                return s1 + s2.Substring(indexOfLast2 + 1);
        }

        // Search for the next possible match
        indexOfLast2 = s2.LastIndexOf(last1, indexOfLast2 - 1);
    }

    // No match found, so concatenate the full strings
    return s1 + s2;
}

此实现在确定需要复制的内容之前不会进行任何字符串复制(部分或其他),这将有助于提高性能。

此外,匹配检查首先测试可能匹配的区域(2个单个字符)的极值,在正常的英语文本中,该极值应能很好地避免检查任何其他字符是否不匹配。

只有当它建立了它能建立的最长匹配,或者根本不可能匹配时,两个字符串才会连接起来。我在这里使用了简单的“+”,因为我认为算法的其余部分的优化已经消除了原始算法中的大部分低效。试一试,让我知道它是否适合你的目的。

FogleBird 15 年前

下面是Python中的一个解决方案。只要不需要一直在内存中构建子字符串,它就应该更快。这项工作是在连接两个字符串的_concat函数中完成的。concat函数是一个连接任意数量字符串的助手。

def concat(*args):
    result = ''
    for arg in args:
        result = _concat(result, arg)
    return result

def _concat(a, b):
    la = len(a)
    lb = len(b)
    for i in range(la):
        j = i
        k = 0
        while j < la and k < lb and a[j] == b[k]:
            j += 1
            k += 1
        if j == la:
            n = k
            break
    else:
        n = 0
    return a + b[n:]

if __name__ == '__main__':
    assert concat('a', 'b', 'c') == 'abc'
    assert concat('abcde', 'defgh', 'ghlmn') == 'abcdefghlmn'
    assert concat('abcdede', 'dedefgh', '') == 'abcdedefgh'
    assert concat('abcde', 'd', 'ghlmn') == 'abcdedghlmn'
    assert concat('abcdef', '', 'defghl') == 'abcdefghl'

bjelli 15 年前

也可以在MySQL中使用以下存储函数执行此操作:

DELIMITER //

DROP FUNCTION IF EXISTS concat_with_overlap //

CREATE FUNCTION concat_with_overlap(a VARCHAR(100), b VARCHAR(100))
  RETURNS VARCHAR(200) DETERMINISTIC
BEGIN 
  DECLARE i INT;
  DECLARE al INT;
  DECLARE bl INT;
  SET al = LENGTH(a);
  SET bl = LENGTH(a);
  IF al=0 THEN 
    RETURN b;
  END IF;
  IF bl=0 THEN 
    RETURN a;
  END IF;
  IF al < bl THEN
     SET i = al;
  ELSE
     SET i = bl;
  END IF;

  search: WHILE i > 0 DO
     IF RIGHT(a,i) = LEFT(b,i) THEN
    RETURN CONCAT(a, SUBSTR(b,i+1));
     END IF;
     SET i = i - 1;
  END WHILE search;

  RETURN CONCAT(a,b);
END//

我用你的测试数据试过了:

mysql> select a,b,c,
    -> concat_with_overlap( concat_with_overlap( a, b ), c ) as result 
    -> from testing //
+-------------+---------+--------+-------------+
| a           | b       | c      | result      |
+-------------+---------+--------+-------------+
| a           | b       | c      | abc         |
| abcde       | defgh   | ghlmn  | abcdefghlmn |
| abcdede     | dedefgh |        | abcdedefgh  |
| abcde       | d       | ghlmn  | abcdedghlmn |
| abcdef      |         | defghl | abcdefghl   |
| abXabXabXac | XabXac  |        | abXabXabXac |
+-------------+---------+--------+-------------+
6 rows in set (0.00 sec)

Phil 15 年前

我认为这会很快:

有两个字符串,string1和string2。通过string1向后(从右到左)查看string2的第一个字符。一旦你有了那个位置,确定是否有重叠。如果没有,你需要继续搜索。如果有,你需要确定是否有可能进行另一场比赛。

要做到这一点,只需探索两个字符串中较短的一个,以便重复出现重叠字符。ie:如果匹配在string1中的位置剩下一个短的string1,则从string1中的新起始点重复初始搜索。相反,如果字符串2的不匹配部分较短,则搜索它以查找重叠字符的重复部分。

根据需要重复。

工作完成!

这不需要太多的内存分配(所有搜索都在适当的位置完成,只需要分配结果字符串缓冲区),并且只需要(最多)传递一个重叠的字符串。

Kirk Broadhurst 15 年前

我正努力使这本书读起来尽可能的愉快。

    public static string Concatenate(string s1, string s2)
    {
        if (string.IsNullOrEmpty(s1)) return s2;
        if (string.IsNullOrEmpty(s2)) return s1;
        if (s1.Contains(s2)) return s1;
        if (s2.Contains(s1)) return s2;

        char endChar = s1.ToCharArray().Last();
        char startChar = s2.ToCharArray().First();

        int s1FirstIndexOfStartChar = s1.IndexOf(startChar);
        int overlapLength = s1.Length - s1FirstIndexOfStartChar;

        while (overlapLength >= 0 && s1FirstIndexOfStartChar >=0)
        {
            if (CheckOverlap(s1, s2, overlapLength))
            {
                return s1 + s2.Substring(overlapLength);
            }

            s1FirstIndexOfStartChar = 
                s1.IndexOf(startChar, s1FirstIndexOfStartChar);
            overlapLength = s1.Length - s1FirstIndexOfStartChar;

        }

        return s1 + s2;
    }

    private static bool CheckOverlap(string s1, string s2, int overlapLength)
    {
        if (overlapLength <= 0)
            return false;

        if (s1.Substring(s1.Length - overlapLength) == 
            s2.Substring(0, overlapLength))
            return true;

        return false;            
    }

编辑:我发现这几乎和杰里JVL的解决方案相同。唯一的区别是,这将适用于“abcde”、“d”情况。

James Black 15 年前

为什么不做这样的事呢? 首先获取三列中的第一个字符或单词(表示重叠)。

然后,开始向StringBuffer添加第一个字符串,一次添加一个字符。

每次查看是否到达与第二个或第三个字符串重叠的部分。

如果是,则开始连接还包含第一个字符串中的内容的字符串。

完成后,如果没有重叠,则从第二个字符串开始,然后是第三个字符串。

所以在问题的第二个例子中,我将把d和g保存在两个变量中。

然后,当我添加第一个字符串时 abc来自第一个字符串,然后我看到d也在第二个字符串中,所以我切换到从第二个字符串添加从字符串2添加def,然后我继续使用字符串3。

如果在数据库中执行此操作,为什么不使用存储过程来执行此操作?

bjelli 15 年前

如果您是在数据库之外执行此操作,请尝试Perl:

sub concat {
  my($x,$y) = @_;

  return $x if $y eq '';
  return $y if $x eq '';

  my($i) = length($x) < length($y) ?  length($x) : length($y);
  while($i > 0) {
      if( substr($x,-$i) eq substr($y,0,$i) )  {
          return $x . substr($y,$i);
      }
      $i--;
  }
  return $x . $y;
}

它和你的算法完全一样,如果Java或Perl更快,我只是好奇而已;

Jonathan 15 年前

这个问题看起来像是最长公共子序列问题的一个变体,可以通过动态规划来解决。

http://www.algorithmist.com/index.php/Longest_Common_Subsequence

monis rahman 11 年前

下面是一个perl-pseudo-oneliner:

$= S1.S2;

S/([\s]+)\1/\1/;

PerlRegex的效率相当高,您可以查找它们使用的算法,但它们确实实现了某种类型的fsm等,因此会得到相当好的o(..)结果。

Alexander Torstling 8 年前

这里是一个Java实现,它发现长度为n和m的两个字符串之间的最大重叠,例如O(min(n,m))操作O(n)。

我和@sepp2k:s有着相同的想法,现在删除了答案,并做了进一步的工作。似乎工作得很好。其思想是迭代第一个字符串,并在找到与第二个字符串开头匹配的内容后开始跟踪。发现如果假匹配和真匹配重叠,可能需要同时执行多个跟踪。最后你选择最长的赛道。

我还没有找出最坏的情况,比赛之间有最大的重叠,但我不希望它螺旋式失控,因为我认为你不能重叠任意多场比赛。通常一次只跟踪一到两个匹配项:一旦出现不匹配,候选项就会被删除。

static class Candidate {
    int matchLen = 0;
}

private String overlapOnce(@NotNull final String a, @NotNull final String b) {
    final int maxOverlap = Math.min(a.length(), b.length());
    final Collection<Candidate> candidates = new LinkedList<>();
    for (int i = a.length() - maxOverlap; i < a.length(); ++i) {
        if (a.charAt(i) == b.charAt(0)) {
            candidates.add(new Candidate());
        }
        for (final Iterator<Candidate> it = candidates.iterator(); it.hasNext(); ) {
            final Candidate candidate = it.next();
            if (a.charAt(i) == b.charAt(candidate.matchLen)) {
                //advance
                ++candidate.matchLen;
            } else {
                //not matching anymore, remove
                it.remove();
            }
        }

    }
    final int matchLen = candidates.isEmpty() ? 0 :
            candidates.stream().map(c -> c.matchLen).max(Comparator.comparingInt(l -> l)).get();
    return a + b.substring(matchLen);
}

private String overlapOnce(@NotNull final String... strings) {
    return Arrays.stream(strings).reduce("", this::overlapOnce);
}

一些测试:

@Test
public void testOverlapOnce() throws Exception {
    assertEquals("", overlapOnce("", ""));
    assertEquals("ab", overlapOnce("a", "b"));
    assertEquals("abc", overlapOnce("ab", "bc"));
    assertEquals("abcdefghqabcdefghi", overlapOnce("abcdefgh", "efghqabcdefghi"));
    assertEquals("aaaaaabaaaaaa", overlapOnce("aaaaaab", "baaaaaa"));
    assertEquals("ccc", overlapOnce("ccc", "ccc"));
    assertEquals("abcabc", overlapOnce("abcabc", "abcabc"));

    /**
     *  "a" + "b" + "c" => "abc"
     "abcde" + "defgh" + "ghlmn" => "abcdefghlmn"
     "abcdede" + "dedefgh" + "" => "abcdedefgh"
     "abcde" + "d" + "ghlmn" => "abcdedghlmn"
     "abcdef" + "" + "defghl" => "abcdefghl"
     */
    assertEquals("abc", overlapOnce("a", "b", "c"));
    assertEquals("abcdefghlmn", overlapOnce("abcde", "defgh", "ghlmn"));
    assertEquals("abcdedefgh", overlapOnce("abcdede", "dedefgh"));
    assertEquals("abcdedghlmn", overlapOnce("abcde", "d", "ghlmn"));
    assertEquals("abcdefghl", overlapOnce("abcdef", "", "defghl"));


    // Consider str1=abXabXabXac and str2=XabXac. Your approach will output abXabXabXacXabXac because by
    // resetting j=0, it goes to far back.
    assertEquals("abXabXabXac", overlapOnce("abXabXabXac", "XabXac"));

    // Try to trick algo with an earlier false match overlapping with the real match
    //  - match first "aba" and miss that the last "a" is the start of the
    // real match
    assertEquals("ababa--", overlapOnce("ababa", "aba--"));
}