Самая длинная общая подпоследовательность оптимизирована
В настоящее время я пытаюсь найти и распечатать самую длинную общую подпоследовательность для 2 заданных строк. Я использую наиболее распространенный алгоритм без рекурсии. Это простая задача, если я сохраняю весь массив, но я пытаюсь немного оптимизировать его и использовать только 2 строки, что вы можете увидеть в коде ниже. С этим изменением поиск длины все еще прост и работает нормально, но восстановление подпоследовательности уже не так просто. Я пытался сделать это несколькими способами, но ни один не помог. Ниже вы можете увидеть мою последнюю попытку. Хотя это работает для тех же самых случаев, есть также случаи, когда это терпит неудачу. После долгого размышления я начинаю верить, что нет способа восстановить подпоследовательность, используя массив только из 2 строк. Мои исследования не дали мне точного ответа, поэтому я спрашиваю, есть ли способ достичь того, что я пытаюсь сделать? Или я застрял с сохранением всего массива, если я хочу напечатать?
//finding length of longest common subsequence
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
if(sequece1[i-1] == sequence2[j-1]) {
tab[i%2][j] = tab[(i-1)%2][j-1] + 1;
} else {
tab[i%2][j] = max(tab[i%2][j-1],tab[(i-1)%2][j]);
}
}
}
//trying to reconstruct longest common subsequence
int last_row = (m-1)%2;
for(int j=n-1; j>0; j--) {
if(tab[last_row][j-1] < tab[last_row][j]) {
if(last_row == 0) {
common_part += sequence2[j];
} else {
common_part += sequence2[j-1];
}
}
}
Решение
Кажется, что не существует простого способа сделать это, потому что, если вы оставите только два последних столбца, существенная часть информации будет потеряна.
Например, рассмотрим два случая: (abcc, acc) строки и (abcc, bcc) строки. Матрица для этих случаев будет
1 1 1 1 and 0 1 1 1
1 1 2 2 0 1 2 2
1 1 2 3 0 1 2 3
Вы видите, что последние два столбца идентичны в обоих случаях, поэтому вы не будете различать эти случаи, судя только по последним двум столбцам. Но нужно их различать, потому что ответы разные (acc а также bcc). Конечно, у вас все еще есть исходные строки, и вы можете использовать информацию оттуда, но я думаю (хотя я не доказал это), что это более или менее эквивалентно поиску LCS для некоторых префиксов исходных строк.
В то же время, есть более продвинутый алгоритм это работает в квадратичном времени и линейном пространстве.
Другие решения