Строковый алгоритм мозаичного размещения

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

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

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

ABC, BCD, DBC 

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

ABC, DBCD

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

ABCD, DBC

Что можно объединить с:

ABCDBC.

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

Думаю, это должно сработать для разбиения двух строк и будет более эффективным, чем ваша текущая реализация с использованием substring и contains. Концептуально я перебираю символы в «левой» строке и сравниваю их с символом в «правой» строке. Если два символа совпадают, я перехожу к следующему символу в правой строке. В зависимости от того, в какой строке был достигнут конец первым, и совпадают ли последние сравниваемые символы или нет, идентифицирован один из возможных случаев мозаичного размещения.

Я не придумал ничего, что могло бы улучшить временную сложность разбиения более чем двух строк. В качестве небольшого примечания для нескольких строк приведенный ниже алгоритм легко расширяется для проверки мозаики одной «левой» строки сразу несколькими «правыми» строками, что может немного предотвратить дополнительный цикл по строкам, если вы пытаетесь выяснить, что делать («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;
        }
    }
}