10405 Longest Common Subsequence
http://acm.uva.es/p/v104/10405.htmlClasico 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
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