Najdłużysz wspólny podciąg


(rafalski) #1

Witam!

Mam takie zadanie:

Dane są dwa ciągi znaków alfanumerycznych zdefiniowanych jako X = oraz Y =

. Znaleźć ich najdłuższy wspólny podciąg.

Plik wejściowy in2a.txt:

● pierwsza linia zawiera dwie przedzielone znakiem spacji nieujemne liczby całkowite n1 oraz

n2 będące długościami dwóch porównywanych ciągów,

● w drugiej oraz trzeciej linii znajdują się odpowiednio pierwszy i drugi ciąg znaków.

Plik wyjściowy out2a.txt:

● pierwsza linia zawiera liczbę całkowitą będącą długością najdłuższego wspólnego podciągu,

● w drugiej linii zapisany jest ciąg wynikowy.

Poszukałem troszkę inforamcji w internecie i udało mi się napisać taki algorytm:

#include 

#include 

#include 


//max(C[i-1][j],C[i][j-1]);



main()

{

      FILE *in, *out;

      int m,n,i,j;

      if ((in=fopen("dane.txt","r"))!=NULL)

      {

         out=fopen("wynik.txt","w");

         fscanf(in,"%d",&n);

         fscanf(in,"%d",&m);

         char s1[n], s2[m];

         fscanf(in,"%s",s1);

         fscanf(in,"%s",s2);


         //printf("%d %d %s %s",n,m,s1,s2); //sprawdzenie czy działa fscanf


         int L[n][m];



         for(i = 0; i <= m; i++) L[i][0] = 0;

  for(j = 0; j <= n; j++) L[0][j] = 0;

  for(i = 1; i < m; i++)

    for(j = 1; j < n; j++)

      if(s1[i] == s2[j])

        L[i][j] = L[i-1][j-1];

      else

        L[i][j] = max(L[i-1][j],L[i][j-1]);


         close(in);

         close(out);

      }

        else

      printf("Blad otwarcia pliku");      

      getchar();

      return 0;

}

Program ma być w C, więc niestety nie działa funkcja max. Może ktoś wie jak ją zadeklarować, bo ja się troszkę pogubiłem. Z góry dziękuje i pozdrawiam!


(Fiołek) #2

Chodzi o max z math.h?

#define max(a, b) (a > b ? a : b)

(Kaka') #3

rafalski ,

Rejestrując się na niniejszym forum zobowiązałeś się przestrzegać jego regulaminu. Niestety, w tym momencie łamiesz go nie tytułując poprawnie tematu. Proszę więc zapoznać się w pierwszej kolejności z całym regulaminem forum, a następnie używając przycisku zmien.gif

W przypadku zignorowania prośby temat poleci do śmietnika oraz mogą zostać wyciągnięte konsekwencje w postaci ostrzeżenia.