Maior Subsequência Comum

Este é outro problema muito clássico de Programação Dinâmica e que deve permanecer na sua cabeça enquanto você participar de competições de programação. Dadas duas sequências s1 e s2, uma de tamanho n e outra de tamanho m, qual a maior subsequência comum às duas? Lembre-se que uma subsequência de s1, por exemplo, é simplesmente um subconjunto dos elementos de s1 na mesma ordem em que apareciam antes. Isto significa que {1, 3, 5} é uma subsequência de {1, 2, 3, 4, 5}, mesmo 1 não estando do lado do 3 na sequência original. Pense um pouco: que parâmetros você escolheria para serem os parâmetros da DP? Se teve uma boa ideia, experimente implementá-la, se não seguem a explicação e o código comentado.

Uma ótima ideia para representarmos os estados da DP são os finais das sequências. Ou seja, implemente uma função lcs (Longest Common Subsequence) que recebe dois inteiros a e b e retorne a maior subsequência comum entre os a primeiros elementos de s1 e os b primeiros elementos de s2. Assim, seja s1={1, 2, 3, 4, 5} e s2={1, 0, 3, -2, 5, 7}. A maior subsequência comum entre elas duas é {1, 3, 5}, pois estamos considerado todos os seu elementos, ou seja, como s1 tem 5 elementos e s2 tem 6,** lcs(5, 6)** retorna 3, que é o comprimento de {1, 3, 5}. Porém, se quiséssemos comparar a sequências só até o 3º termo da primeira e o 4º termo da segunda, ou seja, quiséssemos comparar as sequências {1, 2, 3} e {1, 0, 3, -2}, a maior subsequência comum a elas é {1, 3}, com dois elementos, logo lcs(3, 4) retorna 2.

Imagine que a entrada do problema consiste de três linhas: na primeira estão os inteiros n e m e, nas outras duas seguem n e m inteiros: os elementos de s1 e s2, respectivamente. O programa deve gerar como saída uma única linha com o valor da maior subsequência comum a s1 e s2.

Vamos salvar os elementos de s1 no vetor int s1[MAXN] e os de s2 no vetor int s2[MAXN], onde MAXN é o tamanho máximo das sequências. No caso, vamos definir o valor de MAXN como 1010.

Antes de tudo, lembre-se de salvar os resultados anteriores da função em uma tabela de DP, de nome tab por exemplo, onde teremos o resultado de lcs(a,b) salvo em tab[a][b]. Ela começará com todos os valores iguais a -1, indicando nenhum deles foi calculado ainda. Assim, sempre no começo da função, cheque se aquele estado que você está calculando ainda não foi calculado. Se tiver sido, retorne o valor que você tem salvo para ele.

Desse modo, vamos pensar nos casos bases da DP. É possível calcular o valor da função instantaneamente se a=0 ou se b=0, pois não é possível que haja subsequência de comprimento positivo em uma sequência de nenhum elemento, logo, nesses dois casos, a função deve retornar 0, e guardar o resultado na tabela de DP.

Vejamos agora o caso geral da função. Vamos calcular o valor de lcs(a, b). Cheque se o a-ésimo elemento de s1 é igual ao b-ésimo elemento de s2 (“if(s1[a]==s2[b])”). Se eles forem iguais, então a maior subsequência será exatamente um elemento maior que a maior subsequência entre os a-1 primeiros elementos de s1 e o b-1 primeiros elementos de s2 (pois será exatamente ela somada ao novo elemento comum encontrado, que é s1[a]=s2[b]). Caso contrário, temos duas possibilidades:

  1. A maior subsequência comum termina exatamente no elemento s1[a]. Nesse caso, sabemos que s2[b] não está nela, pois se estivesse, ela terminaria exatamente em s2[b], visto que ele é o último elemento considerado de s2. Assim, não faz nenhuma diferença removermos esse elemento de s2 e recalcularmos a comparação, pois a lcs continuará a mesma. Assim, podemos retornar o valor de lcs(a, b-1), e salvá-lo na tabela de DP.

  2. A maior subsequência comum não termina no elemento s1[a]. Nesse caso, sabemos que s1[a] não está nela, pelo mesmo motivo que s2[b] não estaria, no exemplo anterior. Desse modo, não faz nenhuma diferença removermos s1[a] de s1 e recalcularmos a comparação, pois a lcs continuará a mesma. Assim, podemos retornar o valor de lcs(a-1, b), e salvá-lo na tabela de DP. Dentre as duas possibilidades, retornamos a maior delas! Agora basta implementarmos a função com essa recursão. Segue o código comentado para maior entendimento:

            #include <algorithm>
            using namespace std;
            // defino MAXN como 1010
            #define MAXN 1010
            // declaro as variáveis que vou usar
            int s1[MAXN], s2[MAXN], tab[MAXN][MAXN];
            int lcs(int a, int b){ // declaro a função da DP, de nome lcs
                // se já calculamos esse estado da dp antes
                if(tab[a][b]>=0) return tab[a][b]; // retornamos o valor salvo para ele
                // se uma das sequências for vazia, retornamos zero
                if(a==0 or b==0) return tab[a][b]=0;
                // se s1[a] for igual a s2[b], os retiramos das sequências
                if(s1[a]==s2[b]) return 1+lcs(a-1, b-1); // e adicionamos ele à lcs das subsequâncias restantes
                // se forem diferentes, retorno o máximo entre retirar s1[a] ou s1[b]
                return tab[a][b]=max(lcs(a-1, b), lcs(a, b-1));
            }

Novamente, o mais importante do algoritmo da lcs é a maneira como ele aborda o problema. A ideia de analisar sequências com DP, observando certas propriedades dos seus a primeiros elementos, é muito utilizada em problemas de programação.

Back to top