Алгоритм чередования строк

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

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

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

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

Спасибо заранее.

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

Аналогичный вопрос: Эффективный алгоритм для конкатенации строк с перекрытием

Ответ 1

Закажите строки по первому символу, затем по длине (от самого маленького к самому большому), а затем примените адаптацию к KMP, найденную в этом вопросе о конкатенации перекрывающихся строк.

Ответ 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;
        }
    }
}

Ответ 3

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

Ответ 4

Первое, что нужно спросить, - это если вы хотите найти обработку {CDB, CDA}? Существует не один тиллинг.

Ответ 5

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

ABC, BCD, DBC

Объединение DBC с BCD приводит к:

ABC, DBCD

Что не разрешимо. Но объединение ABC с BCD приводит к:

ABCD, DBC

Что можно комбинировать с:

ABCDBC.