字符串平铺算法

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},操纵这些单词以使上述算法起作用.

类似的问题:带有重叠的字符串连接的高效算法

Answer 1

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