Programação Dinâmica - Maior Subsequência Comum

O problema da maior subsequência comum (longest commom subsequence) (LCS) é o problema de encontrar a maior subsequência comum a duas sequências X e Y. Este é um problema clássico para
compação de arquivos e bioinformática.

Uma subsequência de uma sequência X de caracteres  pode ser obtida removendo alguns caracteres dessa sequência. Por exemplo,

Considere a seguinte sequência X = ABCBDAB, podemos obter  2^|X| subsequência  distintas de X. Por exemplo, BCBDAB e ACDAB são uma subsequência de X.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 100
using namespace std;
int main()
{

    char X [MAX];
    char temp[MAX];
    int m;

    scanf("%s",X);

    m = strlen(X);

    int i,j,index;

    for(i = 0; i < 1<<m ; i++){
        index = 0;
        for(j=0; j<m; j++){
            if( (i & (1<<j)) != 0 ){
              temp[index++] = X[j];
            }
        }
        temp[index] = '\0';
        printf("%s\n",temp);
    }

    return 0;
}

Entrada
BCBD
Saída
B
C
BC
B
BB
CB
BCB
D
BD
CD
BCD
BD
BBD
CBD
BCBD

A solução força bruta consiste em comparar cada subsequencia de X com os símbolos de Y.

Se |X| = m, |Y| = n ,  $2^m$ subsequência de X então a solução força bruta é O(n$2^m$).

Algoritmo Força Bruta

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 100

using namespace std;

int main()
{

    char X [MAX];
    char Y [MAX];
    char temp[MAX];
    char sol[MAX];
    int m;
    int n;
    int maior, cont;
    int index;

    scanf("%s %s",X,Y);

    m = strlen(X);
    n = strlen(Y);

    int i,j;
    maior = 0;

    for(i = 0; i < 1<<m ; i++){
        index = 0;
        for(j=0; j<m; j++){
            if( (i & (1<<j)) != 0 ){
              temp[index++] = X[j];
            }
        }
        temp[index] = '\0';
        printf("%s\n",temp);

        cont = 0;
        for(j=0;j<n && temp[cont]!='\0';j++){
          if(Y[j] == temp[cont]){
            cont++;
          }
        }

        if(temp[cont]=='\0' && cont > maior){
          maior = cont;
          strcpy(sol,temp);
        }

    }


    printf("%d\n",maior);
    printf("%s\n",sol);



    return 0;
}

Entrada
ABCBDAB BDCABA 
Saída
4 
BCBA

Visualmente, a solução ótima pode ser vista da seguinte maneira:

AB-C-BDAB 
 | | | |
-BDCAB-A- 

Para diminuir a complexidade para resolver este problema, primeiramente, precisamos encontrar uma maneira de decompor o problema grande em termos de subproblemas menores de tal maneira que a solução ótima do problema maior dependa da solução ótima de subproblemas menores. Essa propriedade chamamos de subestrutura ótima.

Definição do problema c[i,j] = problema de encontrar a maior subsequencia comum das seguintes sequência X[1..i] e Y[1..j]. Essas duas sequências são sequências prefixos das sequências inicias.

Subsestrutura Ótima
Caso Base:

• Se i=0 ou j=0 então c[i,j] = 0. Se umas das sequências é nula então a maior sequência comum também é nula.

• Se X[i]=X[j] então c[i,j] = c[i-1,j-1] + 1. Se o último caracter for igual nas duas sequências então este caractere está na maior subsequencia comum e podemos reduzir o problema para c[i-1,j-1].

• Se X[i]!=X[j] então c[i,j] = max(c[i,j-1],c[i-1,j]). Se o último caracter não for igual nas duas sequências então temos duas opções: 
• deletamos o último caractere da sequência Y e comparamos com a sequência X completa(c[i,j-1])  
• deletamos o último caractere da sequência X e comparamos com a sequência Y completa(c[i-1,j])

          A solução ótima será dada pelo máximo entre os dois subproblemas.

Algoritmo programação dinâmica

    int n,m;
    int i,j;

    scanf("%s",X);
    scanf("%s",Y);
    
    n = strlen(X);
    m = strlen(Y);

    for(i=0;i<=n;i++)
      c[i][0] = 0;

    for(j=0;j<=m;j++)
      c[0][j] = 0;


    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
        if(X[i-1]==Y[j-1])
          c[i][j] = c[i-1][j-1] + 1;
        else
          c[i][j] = max( c[i-1][j] , c[i][j-1]);



    printf("%d\n",c[n][m]);

Entrada
ABCBDAB BDCABA
Saída
 4

A tabela com todos os subproblemas obtida é:

c		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

Consultando a tabela, podemos descobrir a solução do problema lcs('AB','BD') = 1 (vermelho) ou do problema lcs('ABCB','BDCAB') = 3 (azul).

A maior subsequência comum pode ser extraída da tabela da seguinte maneira:

i = n;
j = m;

stack <char> pilha;

while(i!=0 && j!=0){
   if(X[i-1]==Y[j-1]){
      pilha.push(X[i-1]);
      i--;
      j--;
    }else if(c[i-1][j] > c[i][j-1]){
      i--;
    }else{
      j--;
    }
}

while( !pilha.empty() ){
    cout << pilha.top() ;
    pilha.pop();
}
cout << endl;

A maior subsequência comum pode ser obtida recursivamente da seguinte maneira:

void lcs(int i,int j){
  if(i!=0 && j!=0){
      if(X[i-1]==Y[j-1]){
        lcs(i-1,j-1);
        printf("%c",X[i-1]);
      }else if(c[i-1][j] > c[i][j-1]){
        lcs(i-1,j);
      }else{
        lcs(i,j-1);
      }
  }
}

Chamada
lcs(n,m);
cout << endl;

Para calcular a solução de um subproblema em particular, precisamos apenas de duas linhas para obter a solução dos subproblemas c[i-1,j], c[i,j-1], c[i-1,j-1]. Podemos otimizar a utilização da memória aproveitando este fato da seguinte maneira:

char X[MAXN];
char Y[MAXN];
int c[2][MAXN];

int n,m;
int i,j;

scanf("%s",X);
scanf("%s",Y);

n = strlen(X);
m = strlen(Y);

for(j=0;j<=m;j++)
  c[0][j] = 0;

for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    if(X[i-1]==Y[j-1])
      c[i&1][j] = c[(i-1)&1][j-1] + 1;
    else
       c[i&1][j] = max(c[(i-1)&1][j] , c[i&1][j-1]);

printf("%d\n",c[n&1][m]);

Este problema tem variações interessantes:

• Encontrar a menor supersequência comum entre duas string. Por exemplo, a menor supersequência comum entre AAATTT e GAATCT é GAAATCTT. Observe que AAATTT e GAATCT são subsequência de GAAATCTT e GAAATCTT é a menor sequência com essa propriedade.Esse problema foi explorado em: http://br.spoj.pl/problems/PARQUE/
•  Encontrar a menor distância entre duas strings A e B. A distância entre duas string é dada pelo menor número de operações necessária para transformar A em B. As operações permitidas são deletar um caractere, adicionar um caractere ou substituir um caractere por outro. Pode ser encontrado aqui: http://www.spoj.pl/problems/EDIST/

Links interessantes:

• http://cs.nyu.edu/~yap/classes/funAlgo/05f/lect/l7.pdf
• http://comscigate.com/Books/contests/icpc.pdf