algorithm - 字符串平铺算法

Question

我正在寻找一种有效的算法来进行字符串平铺。基本上，您会得到一个字符串列表，例如BCD, CDE, ABC, A，并且生成的平铺字符串应该是ABCDE，因为BCD与CDEyielding对齐BCDE，然后与ABCyield final对齐ABCDE。

目前，我正在使用一种稍微幼稚的算法，其工作原理如下。从一对随机字符串开始，比如BCDand CDE，我使用以下（在 Java 中）：

public static String tile(String first, String second) {
  for (int i = 0; i < first.length() || i < second.length(); i++) {
    // "right" tile (e.g., "BCD" and "CDE")
    String firstTile = first.substring(i);
    // "left" tile (e.g., "CDE" and "BCD")  
    String secondTile = second.substring(i);
    if (second.contains(firstTile)) {
      return first.substring(0, i) + second;
    } else if (first.contains(secondTile)) {
      return second.substring(0, i) + first;
    }
  }
  return EMPTY;
}

System.out.println(tile("CDE", "ABCDEF")); // ABCDEF
System.out.println(tile("BCD", "CDE")); // BCDE
System.out.println(tile("CDE", "ABC")); // ABCDE
System.out.println(tile("ABC", tile("BCX", "XYZ"))); // ABCXYZ

虽然这可行，但它不是很有效，因为它一遍又一遍地迭代相同的字符。

那么，有没有人知道更好（更有效）的算法来做到这一点？这个问题类似于 DNA 序列比对问题，因此非常欢迎该领域（当然还有其他人）提供任何建议。另请注意，我不是在寻找一个对齐，而是一个平铺，因为我需要一个字符串完全重叠在另一个上。

我目前正在寻找Rabin-Karp 算法的改编版本，以提高算法的渐近复杂度，但在进一步研究这个问题之前，我想听听一些建议。

提前致谢。

对于存在歧义的情况——例如，{ABC, CBA}可能导致ABCBA或CBABC——，可以返回任何平铺。但是，这种情况很少发生，因为我正在平铺单词，例如{This is, is me} => {This is me}，这些单词被操纵以便上述算法起作用。

类似问题：Efficient Algorithm for String Concatenation with Overlap

score 4 · Accepted Answer

按第一个字符排序字符串，然后是长度（从最小到最大），然后将适配应用于此问题中关于连接重叠字符串的 KMP。

score 2 · Accepted Answer

我认为这应该适用于两个字符串的平铺，并且比使用子字符串和包含的当前实现更有效。从概念上讲，我遍历“左”字符串中的字符并将它们与“右”字符串中的字符进行比较。如果这两个字符匹配，我将移动到正确字符串中的下一个字符。根据第一次到达末尾的字符串，以及最后比较的字符是否匹配，确定可能的平铺情况之一。

我没有想到任何可以提高平铺两个以上字符串的时间复杂度的方法。作为多个字符串的一个小注释，下面的这个算法很容易扩展为一次检查单个“左”字符串与多个“右”字符串的平铺，如果你试图的话，这可能会防止额外的字符串循环通过尝试所有的可能性，找出是做 ("ABC", "BCX", "XYZ") 还是 ("ABC", "XYZ", BCX")。一点点。

string Tile(string a, string b)
{
    // Try both orderings of a and b,
    // since TileLeftToRight is not commutative.

    string ab = TileLeftToRight(a, b);

    if (ab != "")
        return ab;

    return TileLeftToRight(b, a);

    // Alternatively you could return whichever
    // of the two results is longest, for cases
    // like ("ABC" "BCABC").
}

string TileLeftToRight(string left, string right)
{
    int i = 0;
    int j = 0;

    while (true)
    {
        if (left[i] != right[j])
        {
            i++;

            if (i >= left.Length)
                return "";
        }
        else
        {
            i++;
            j++;

            if (i >= left.Length)
                return left + right.Substring(j);

            if (j >= right.Length)
                return left;
        }
    }
}

score 1 · Accepted Answer

如果开源代码是可以接受的，那么您应该检查斯坦福STAMP基准套件中的基因组基准：它几乎完全符合您的要求。从一堆字符串（“基因”）开始，它寻找包含所有基因的最短字符串。例如，如果您有 ATGC 和 GCAA，它会找到 ATGCAA。该算法没有将其限制为 4 个字符的字母表，因此这应该可以帮助您。

score 0 · Accepted Answer

有趣的问题。你需要某种回溯。例如，如果您有：

ABC, BCD, DBC

将 DBC 与 BCD 相结合会产生：

ABC, DBCD

这是无法解决的。但是将 ABC 与 BCD 结合会导致：

ABCD、DBC

可以组合成：

ABCDBC.

score 0 · Accepted Answer

0

首先要问的是要不要找到{CDB, CDA}的耕种？没有单一的耕作。

于 2009-09-17T20:48:53.297 回答

algorithm - 字符串平铺算法

5 回答 5

Related

Reference