Voltar

Maior subsequência comum - Paradigmas

0 Curtidas
/* Dynamic Programming: Longest Common Subsequence
   =================================================================
   Description: Given two arrays A and B with sizes n and m 
                respectively, compute the length of the longest
common subsequence.  This routine also returns in 
the array 's' a longest common subsequence (it
may not be unique).  One can specify which one to
choose when multiply longest common subsequences
exist.
   
   Complexity:  O(N*M)
   -----------------------------------------------------------------
   Author:      Howard Cheng, Gilbert Lee
   Date:        Nov 19, 2002
   References:  www.ics.uci.edu/~eppstein/161/960229.html
   -----------------------------------------------------------------
   Reliability: 2 (Spanish Problem 10405, 10066) Dec 2002
   Notes:       - Added way to change type of array
*/

#include 
#include 

#define MAXN 20
#define Atype int
#define max(x,y) (((x)>(y))?(x):(y))

int LCS(Atype *A, int n, Atype *B, int m, Atype *s)
{
  int L[MAXN+1][MAXN+1];
  int i, j, k;
  
  for(i = n; i >= 0; i--) for(j = m; j >= 0; j--){
    if(i == n || j == m){
      L[i][j] = 0;
    } else if(A[i] == B[j]){
      L[i][j] = 1 + L[i+1][j+1];
    } else {
      L[i][j] = max(L[i+1][j], L[i][j+1]);
    }
  }
  
  /* The following is not needed if you are not interested in
     a longest common subsequence */

  k = 0;
  i = j = 0;
  while(i < n && j < m){
    if(A[i] == B[j]){
      s[k++] = A[i++];
      j++;
    } else if(L[i+1][j] > L[i][j+1]){
      i++;
    } else if(L[i+1][j] < L[i][j+1]){
      j++;
    } else {
      /* put tie-breaking conditions here */
      
      /* eg. pick the one that starts at the first one the earliest */
      j++;
    }
  }
  return L[0][0];
}

int main(void)
{
  Atype A[MAXN], B[MAXN], s[MAXN];
  int m, n, i, l;

  while (scanf("%d %d", &n, &m) == 2 && 1 <= n && 1 <= m &&
 n <= MAXN && m <= MAXN) {
    for (i = 0; i < n; i++) scanf("%d", &A[i]);
    for (i = 0; i < m; i++) scanf("%d", &B[i]);
    l = LCS(A, n, B, m, s);
    for (i = 0; i < l; i++) printf("%d ", s[i]);
    printf("\nLen = %d\n", l);
  }
  return 0;
}
Problemas relacionados
  Nome Comentário
Ainda não há nenhum problema relacionado a esse conteúdo

Comentários


Postagens neste fórum só são permitidas para membros com conta ativa. Por favor, efetue login or cadastro para postar.