Блог

Я реализовал решение динамического программирования, чтобы найти самую длинную общую подпоследовательность среди 2 строк. По-видимому, есть способ обобщить этот алгоритм, чтобы найти LCS среди 3 строк, но в моих исследованиях я не нашел никакой информации о том, как это сделать. Любая помощь будет оценена.

Чтобы найти самую длинную общую подпоследовательность (LCS) из 2 строк A и B, вы можете пройти 2-мерный массив по диагонали, как показано в опубликованной вами ссылке. Каждый элемент в массиве соответствует задаче нахождения LCS подстрок A’ и B’ (A сокращается по номеру строки, B сокращается по номеру столбца). Эта проблема может быть решена путем вычисления значения всех элементов в массиве. Вы должны быть уверены, что при вычислении значения элемента массива все подзадачи, необходимые для вычисления этого заданного значения, уже решены. Вот почему вы проходите 2-мерный массив по диагонали.

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

Вместо того, чтобы перебирать N-мерный массив в специальном порядке, вы также можете решить проблему рекурсивно. При рекурсии важно сохранить промежуточные решения, поскольку для многих ветвей потребуются одни и те же промежуточные решения. Я написал небольшой пример на C #, который делает это:

 string lcs(string[] strings)
{
    if (strings.Length == 0)
        return "";
    if (strings.Length == 1)
        return strings[0];
    int max = -1;
    int cacheSize = 1;
    for (int i = 0; i < strings.Length; i  )
    {
        cacheSize *= strings[i].Length;
        if (strings[i].Length > max)
            max = strings[i].Length;
    }
    string[] cache = new string[cacheSize];
    int[] indexes = new int[strings.Length];
    for (int i = 0; i < indexes.Length; i  )
        indexes[i] = strings[i].Length - 1;
    return lcsBack(strings, indexes, cache);
}
string lcsBack(string[] strings, int[] indexes, string[] cache)
{
    for (int i = 0; i < indexes.Length; i   )
        if (indexes[i] == -1)
            return "";
    bool match = true;
    for (int i = 1; i < indexes.Length; i  )
    {
        if (strings[0][indexes[0]] != strings[i][indexes[i]])
        {
            match = false;
            break;
        }
    }
    if (match)
    {
        int[] newIndexes = new int[indexes.Length];
        for (int i = 0; i < indexes.Length; i  )
            newIndexes[i] = indexes[i] - 1;
        string result = lcsBack(strings, newIndexes, cache)   strings[0][indexes[0]];
        cache[calcCachePos(indexes, strings)] = resu<
        return resu<
    }
    else
    {
        string[] subStrings = new string[strings.Length];
        for (int i = 0; i < strings.Length; i  )
        {
            if (indexes[i] <= 0)
                subStrings[i] = "";
            else
            {
                int[] newIndexes = new int[indexes.Length];
                for (int j = 0; j < indexes.Length; j  )
                    newIndexes[j] = indexes[j];
                newIndexes[i]--;
                int cachePos = calcCachePos(newIndexes, strings);
                if (cache[cachePos] == null)
                    subStrings[i] = lcsBack(strings, newIndexes, cache);
                else
                    subStrings[i] = cache[cachePos];
            }
        }
        string longestString = "";
        int longestLength = 0;
        for (int i = 0; i < subStrings.Length; i  )
        {
            if (subStrings[i].Length > longestLength)
            {
                longestString = subStrings[i];
                longestLength = longestString.Length;
            }
        }
        cache[calcCachePos(indexes, strings)] = longestString;
        return longestString;
    }
}
int calcCachePos(int[] indexes, string[] strings)
{
    int factor = 1;
    int pos = 0;
    for (int i = 0; i < indexes.Length; i  )
    {
        pos  = indexes[i] * factor;
        factor *= strings[i].Length;
    }
    return pos;
}
 

Мой пример кода может быть оптимизирован дальше. Многие из кэшируемых строк являются дубликатами, а некоторые являются дубликатами с добавлением только одного дополнительного символа. Это использует больше места, чем необходимо, когда входные строки становятся большими.

При вводе: «666222054263314443712», «5432127413542377777», «6664664565464057425»

Возвращаемый LCS равен «54442»