Струны и алгоритм динамического программирования

Question

Строка Z - это слияние двух других строк X и Y, если Z - это конкатенация подстрок X и Y по порядку.Например, «strMERingGE» - это объединение «строки» и «MERGE».Дайте алгоритм динамического программирования, который берет 3 строки и проверяет, является ли третье слияние первых двух.

Эта проблема выглядит как вариант самой длинной общей проблемы подпоследовательности, я пробовал этот алгоритм, но я не увереноб этом.

public static String concat(String s1, String s2) {
if (string.IsNullOrEmpty(s1))
    return s2;
if (string.IsNullOrEmpty(s2) )
    return s1;



int len1 = s1.Length - 1;
char last1 = s1[len1];
char first2 = s2[0];


    if (s1[len1 - indexOfLast2] == first2)
    {

int inLast2 = s2.LastIn(last1, Math.Min(len1, s2.Length - 1));
while (inLast2 != -1)
{
        int x = inLast2;
        while ((x != -1) && (s1[len1 - inLast2 + x] == s2[x]))
            x--;
        if (x == -1)
            return s1 + s2.Substring(Last2 + 1);
    }
inLast2 = s2.LastIn(last1, inLast2 - 1);

}


if ( s1 + s2.Substring(Last2 + 1) == 2)
return inLast2  +1;

Answer 1

Используйте эту рекурсию динамического программирования:

Соответствие (i, j) = Соответствие (i-1, j) И (Z [i + j] == X [i]) ИЛИ Соответствие (i,j-1) AND (Z [i + j] == Y [j])

Это даст двумерную двоичную матрицу.Если между концом и началом есть путь (непрерывный True, только вверх или влево, а не поперек), существует решение (решение, полученное путем перевода соответствий X и слева в Y).

PS: использоватьследующая функция и матрица автоматически запомнят путь:

Match(i,j) = 
    if Match(i-1,j) AND (Z[i+j] == X[i]):
        1
    elif Match(i,j-1) AND (Z[i+j] == Y[j]):
        2
    else:
        0

Answer 2

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

Если длины X и Y равны m и n, создайте (m + 1) -by- (n + 1) матрицу. Начиная с ячейки (i, j) = (0,0), обойдите Z и переместите одну ячейку вправо (j + 1) в матрице, если текущий символ равен X [j], и одну вниз (i + 1), если текущий символ равен Y [i]. Выведите значение true, если вы окажетесь в ячейке (m + 1, n + 1), и значение false, если вы не можете сопоставить символ ни в одной строке в любой точке или окажетесь в другой ячейке.

Алгоритм редактирования расстояния, который очень похож, см .: http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 3

Я не изучал ваши вещи, но действительно чувствую, что это можно решить с помощью алгоритма LCS. На самом деле, что вам нужно выяснить это:

• Является ли LCS (Z, Y) == Y
• Является ли LCS (Z, X) == X
• отсортировано (X + Y) == отсортировано (Z)

Интуитивно кажется, что это помогает ...