Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión

 
Búsqueda Avanzada

15.707 Mensajes en 3.130 Temas- por 371 Usuarios - Último usuario: lasfirrot
Mayo 18, 2012, 04:02:10
Foro de Hispabyte.netProgramaciónCompeticiones de programación y algorítmicaACM UVATema: 10405 Longest Common Subsequence
Páginas: [1]   Ir Abajo
Imprimir
Autor Tema: 10405 Longest Common Subsequence  (Leído 1281 veces)
0 Usuarios y 1 Visitante están viendo este tema.
HQH
Administrator
Miembro Imprescindible
*****
Mensajes: 1.813



Ver Perfil
« : Agosto 14, 2006, 07:45:08 »


10405 Longest Common Subsequence
http://acm.uva.es/p/v104/10405.html

Clasico programa de programacion Dinamica.

Debemos ejecutar el algoritmo para obtener las mas Subsecuencias comunes mas largas.


Posteo codigo y una traza de un ejemplo inventado
Código:
int maxcomsub()
{
    int tam1,tam2;
    short int vt[1001][1001];
    tam1=strlen(s1);
    tam2=strlen(s2);
    for(int i=0;i<tam1;i++)
    {
       for(int j=0;j<tam2;j++)
       {
           vt[i][j]=0;
       }
    }
    
    for(int i=tam1;i>=0;i--)
    {
        for(int j=tam2;j>=0;j--)
        {
             if(s1[i]==0 || s2[j]==0)
             {
                         vt[i][j]=0;
             }
             else if(s1[i]==s2[j])
             {
                  vt[i][j]=1+vt[i+1][j+1];
             }
             else
             {
                  vt[i][j]=maximo(vt[i+1][j],vt[i][j+1]);
             }
        }
    }
    
    return vt[0][0];
    
}

La traza es la siguiente

Traza de ejemplo

abcf
ncab


abcf
21100n
21100c
20000a
11000b
00000
« Última modificación: Agosto 14, 2006, 07:45:49 por ]_HQH_[ » En línea
Páginas: [1]   Ir Arriba
Imprimir
Foro de Hispabyte.netProgramaciónCompeticiones de programación y algorítmicaACM UVATema: 10405 Longest Common Subsequence
Ir a:  


Tema diseñado por RJ-45 para Hispabyte.net basado en el
theme famouspadexx v.09 designed by Formado Comprido
Downloable here. My present to padexx.de