Cod sursa(job #340618)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 15 august 2009 18:01:31
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<stdio.h>
int m;
int n;
int solutie[1028];
int mat[1026][1026];
char wh[1026][1026];
int contor;
int A[1026];
int B[1026];
int i;
int j;
int maxim(int x1, int y1)
{
    if (x1 > y1) return x1;
    return y1;
}

int main()
{
    freopen("cmlsc.in","r",stdin);
    freopen("cmlsc.out","w",stdout);

    scanf("%d %d",&m,&n);

    for(int i = 1; i <= m; i++)
     scanf("%d",&A[i]);
    for(int i = 1; i <= n; i++)
     scanf("%d",&B[i]);
    for(int i = 1; i <= m; i++)
     for(int j = 1; j <= n; j++)
     {
       if (A[i] == B[j])
       {
           mat[i][j] = mat[i-1][j-1] + 1;

       }
          else
           {
           mat[i][j] = mat[i-1][j-1];
           }
       wh[i][j] = 1;
       if (mat[i-1][j] > mat[i][j])
        {
            mat[i][j] = mat[i-1][j];
            wh[i][j] = 2;
        }
       if (mat[i][j-1] > mat[i][j])
        {
            mat[i][j] = mat[i][j-1];
            wh[i][j] = 3;
        }
      }
      i = m;
      j = n;
      printf("%d\n",mat[i][j]);
      while (contor < mat[m][n])
       {

           if (wh[i][j] == 1)
           {
            if (A[i] == B[j]) {solutie[++solutie[0]] = A[i];
            contor++;
            }
            i--;
            j--;
           }
           else
            if (wh[i][j] == 2)
             {
                 i--;
             }
             else
              j--;
       }
    for(int i = solutie[0]; i >= 1; i--)
     printf("%d ",solutie[i]);
    return 0;
}