[C] najdluzszy wspolny podciag

[soundluk]

musze napisac program ktory wypisze najdluzszy wspolny podciag, napisalem go na podstawie algorytmow z wiki. cos jest nie tak. co konkretnie zmienic w kodzie?

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

int max(int a, int b)
{ if (a>b)
  { return a; } else
  { return b; }
}

int main(int argc, char *argv[2])
{
  char* t="abaabbaaa";
  char* s="babab";
  int i,j,n=strlen(t),m=strlen(s);
  int d[n][m];
  
  
  for(i=0; i<n; i++)
  { d[i][0]=0; }
  for(j=0; j<m; j++)
  { d[0][j]=0; }  
  
  for(i=1; i<n; i++)
  {
    for(j=1; j<m; j++)
    {
      if(t[i]==s[j])
      { d[i][j]=d[i-1][j-1]+1; }         
      else { d[i][j]=max(d[i-1][j],d[i][j-1]); }
    }         
  }        

int p[100];
int c=0;

  i=n;
  j=m;
  while(i>0 && j>0)
  {
    if(t[i]==s[j])
    {
      p[c]=t[i];
      i--;
      j--;
      c++;
    } else
       {
       if (d[i-1][j]>d[i][j-1]) 
         { i--; }
       else
         { j--; }
       }
   }
for(i=0; i<5; i++)
{ printf("%c", p[i]); }

printf("
");

  system("pause");
  return 0;
}

[matshadow]

[wafello]

A co konkretnie jest nie tak? - zły algorytm czy kompilator ma problemy?

[smiechowiec]

A co konkretnie jest nie tak? - zły algorytm czy kompilator ma problemy?

Sprawdziłem sam algorytm i niestety posiada pewne wady.
Najpierw sam program

char* t="abaabbaaa";
char* s="babab";

Tak nigdy nie pisz, bo wartości trzeba zadeklarować w zmiennej więc powinno być tak

Kod: Zaznacz cały

char t[]="abaabbaaa";
char s[]="babab";

Przed petlą
i=n;
j=m;
powinno być
i=n - 1;
j=m - 1;

Po tych poprawkach algorytm dla podanego ciągu zwraca szukany ciąg, ale od końca, bo pętla while przeszukuje z jakiegoś powodu ciągi od końca.

Kolejny błąd tkwi w braku resetowania licznika c dla nowego dłużeszgo ciągu.
Do zmiennej wynikowej dodawane są kolejne pasujące znaki, ale gdy napotkamy kolejny ciąg, poprzedni nadal zostaje.
zamiast for(i=0; i<5; i++)
mozna podać for(i=0; i<c; i++)