Cod sursa(job #1998198)

Utilizator morosanucipiMorosanu Cipi morosanucipi Data 6 iulie 2017 21:51:25
Problema Cel mai lung subsir comun Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.83 kb
#include <stdio.h>
#include <stdlib.h>
FILE * out;
int ** s;
int ** LCS(int *a,int lengthA,int *b,int lengthB)
{
    int m=lengthA;
    int n=lengthB;
    int **c=(int **)calloc(m+1,sizeof(int*));
    s=(int **)calloc(m+1,sizeof(int*));
    for(int i=0; i<m+1; i++)
    {
        c[i]=(int *)calloc(n+1,sizeof(int));
        s[i]=(int *)calloc(n+1,sizeof(int));
    }
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
        {
            if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
                s[i][j]=7;
            }
            else
            {
                if(c[i-1][j]>=c[i][j-1])
                {
                    c[i][j]=c[i-1][j];
                    s[i][j]=8;
                }
                else
                {
                    c[i][j]=c[i][j-1];
                    s[i][j]=6;
                }
            }

        }
    return c;
}
void LCS_Print(int *a,int i,int j)
{
    if(i==0 || j==0)
    {
        return;
    }
    if(s[i][j]==7)
    {
        LCS_Print(a,i-1,j-1);
        fprintf(out,"%d ",a[i-1]);
    }
    else
    {
        if(s[i][j]==8)
        {
            LCS_Print(a,i-1,j);
        }
        else
        {
            LCS_Print(a,i,j-1);
        }
    }
}
int main()
{
    FILE * in = fopen("cmlsc.in","r");
    out = fopen("cmlsc.out","w");
    int m,n;
    fscanf(in,"%d %d",&m,&n);
    int * a=(int *)calloc(m,sizeof(int));
    int * b=(int *)calloc(n,sizeof(int));
    for(int i=0; i<m; i++)
    {
        fscanf(in,"%d",&a[i]);
    }
    for(int i=0; i<n; i++)
    {
        fscanf(in,"%d",&b[i]);
    }
    int **c=LCS(a,m,b,n);
    fprintf(out,"%d\n",c[m][n]);
    LCS_Print(a,m,n);
    free(c);
    free(s);
    free(a);
    free(b);
    fclose(in);
    fclose(out);
    return 0;
}