字符串平铺算法

Question

我正在寻找一种高效的算法来进行字符串平铺。基本上，您将获得一组字符串，例如BCD、CDE、ABC、A，生成的平铺字符串应为ABCDE，因为BCD与CDE对齐产生BCDE，然后与ABC对齐产生最终的ABCDE。

目前，我正在使用一个稍微朴素的算法，它的工作方式如下。从随机一对字符串开始，比如BCD和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}，以保证上述算法能够正常运行。

类似问题：高效字符串重叠拼接算法

- João Silva

---

+1 如果问题写得好（但真的是为了找到 ï 键 8-) - RichieHindle

在 OS X 中，键盘上输入 umlaut 字符 ï 的方法为先按下 Alt+u 键，然后再输入要添加该字符的字母 i。 - Hank Gay

非常接近于https://dev59.com/UHM_5IYBdhLWcg3wp0-l。 - Daniel C. Sobral

Answer 1

根据首字母、长度（从小到大）对字符串进行排序，然后应用在此问题中找到的适用于KMP的改进方法来连接重叠的字符串。

- Daniel C. Sobral

---

谢谢，我一直在寻找关于平铺和对齐的问题，但是没能找到。 - João Silva

找到它确实很困难。幸运的是，我已经回答过它了，所以搜索范围缩小了一些。 - Daniel C. Sobral

Answer 2

我认为这种方法适用于两个字符串的平铺，并且比您当前使用子字符串和包含函数的实现更有效。从概念上讲，我循环遍历“左”字符串中的字符，并将它们与“右”字符串中的字符进行比较。如果两个字符匹配，我就移动到右侧字符串中的下一个字符。根据哪个字符串首先到达结尾，以及最后比较的字符是否匹配，可以识别出可能的平铺情况之一。

我还没有想到任何方法来提高平铺多于两个字符串的时间复杂度。对于多个字符串，以下算法可以轻松扩展到一次检查单个“左”字符串与多个“右”字符串的平铺，这可能会稍微减少对字符串的额外循环，如果你只是尝试找出是否要做（“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;
        }
    }
}

- Joren

Answer 3

如果可以接受开源代码，那么你应该检查斯坦福大学STAMP基准测试套件中的基因组基准测试：它几乎完全符合您的要求。从一堆字符串（“基因”）开始，它寻找包含所有基因的最短字符串。例如，如果您有ATGC和GCAA，则会找到ATGCAA。算法没有任何限制，可以帮助您处理任意长度的字符集。

- redtuna

Answer 4

首先要问的是，您是否想找到 {CDB, CDA} 的瓦片？没有单一的瓦片。

- user172818

---

不，我需要其中一个字符串完全重叠。使用我的算法，这对字符串将返回空字符串。 - João Silva

这对 {ABC, CBA} 的输出是什么？也因为歧义而为空吗？那 {ABC, BCA} 呢？更喜欢 ABCA，因为重叠部分更长？您允许不完美的匹配吗？没有完整的问题描述，很难进一步进行。 - user172818

@JG：如果您主要考虑两个字符串，可以为第一个字符串构建后缀树，并针对后缀树扫描第二个字符串。时间复杂度为O（L），其中L是两个字符串的总长度。 - user172818

@JG：我意识到你可能也会使用KMP算法，这个算法更容易实现。时间复杂度也应该是线性的。 - user172818

@lh3: 我已经研究了KMP算法，通过消除重复的substring调用，确实可以提高算法的运行时间。现在，关于布鲁金图，能否解释一下如何在这种情况下利用它？ - João Silva

Answer 5

有趣的问题。你需要一些回溯算法。例如，如果你有：

ABC, BCD, DBC 

将DBC与BCD相结合的结果是：

ABC, DBCD

这是无法解决的。但将ABC与BCD相结合会产生以下结果：

ABCD、DBC

可以将它们结合为：

ABCDBC.

- Toon Krijthe

---

是的，我需要深入研究一下。另一种选择是生成字符串的所有 n! 种排列，然后对于每种可能的排列从左到右进行处理，但这显然非常慢。 - João Silva