Алгоритм строчной черепицы

Question

Я ищу эффективный алгоритм, который можно сделать string tiling. В принципе, вы получаете список строк, скажете 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 

Хотя это работает, это не очень эффективное, так как он перебирает те же символы, снова и снова.

Итак, кто-нибудь знает лучший (более эффективный) алгоритм для этого? Эта проблема аналогична проблеме выравнивания последовательности ДНК, поэтому любые советы от кого-то в этой области (и другие, конечно) очень приветствуются. Также обратите внимание, что я не ищу выравнивание , но tiling, потому что мне требуется полное перекрытие одной из строк над другой.

В настоящее время я ищу адаптацию Rabin-Karp algorithm, чтобы улучшить асимптотическую сложность алгоритма, но я хотел бы услышать некоторые советы, прежде чем углубляться в этот вопрос.

Заранее спасибо.

---

В ситуациях, когда существует неоднозначность - например, {ABC, CBA}, которые могли бы привести к ABCBA или CBABC - любая черепица может быть возвращен. Однако эта ситуация редко встречается, потому что я пишу слова, например. {This is, is me} => {This is me}, которые управляются так, что работает вышеупомянутый алгоритм.

Похожий вопрос: Efficient Algorithm for String Concatenation with Overlap

Answer 1

Первое, что нужно спросить, если вы хотите найти возделывание {CDB, CDA}? Нет единого размола.

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; 
     } 
    } 
} 

Answer 3

Заказать строки по первому символу, то длина (от наименьшего к наибольшему), а затем применить приспособление к КМР находится в this question о конкатенации перекрывающихся строк.

Answer 4

Интересная проблема. Вам нужно какое-то отступление. Например, если у вас есть:

ABC, BCD, DBC 

Объединение DBC с результатами BCD в:

ABC, DBCD 

который не разрешимы. Но сочетание ABC с результатами BCD в:

ABCD, DBC

Какие могут быть объединены:

ABCDBC. 

Answer 5

Если Открытый исходный код является приемлемым, то вы должны проверить генома ориентиры в Стэнфорде STAMP эталонный набор: он делает в значительной степени именно то, что вы ищете. Начиная с пучка строк («генов»), он ищет кратчайшую строку, содержащую все гены. Например, если у вас есть ATGC и GCAA, он найдет ATGCAA. Нет ничего о алгоритме, который ограничивает его 4-символьным алфавитом, поэтому это должно помочь вам.