Użytkownik:Korwin/NWP

//A1 - slowo dlugosci d1 //A2 - slowo dlugosci d2

1. include<stdio.h>
2. include<stdlib.h>

class Stos {

   struct StosElm
   {
      StosElm *nast;
      char znak;
      StosElm(char z, StosElm *n)
      {
           znak = z;
           nast = n;        
      }
   };       
   
   StosElm* top;
   public:
   Stos() { top = 0; }
   void Put(char z) 
   { 
        StosElm* h; 
        h = new StosElm(z,top); 
        top = h;  
   }
   bool Empty() { return !top; }
   char Pop() { char c = top->znak; top = top->nast; return c;}

};

int main() {

 unsigned long d1, d2,i,j;
 char *A1,*A2;
 
 scanf("%d",&d1);    
 A1 = new char[d1];  
 scanf("%s",A1);

 scanf("%d",&d2);  
 A2 = new char[d2];
 scanf("%s",A2);

// printf("1: (%d) %s 2: (%d) %s\n",d1,A1,d2,A2);

 unsigned D[d1+1][d2+1];

// wpisywanie stanow poczatkowych

 for(i=0;i<=d1;i++) D[i][0]=0;
 for(j=0;j<=d2;j++) D[0][j]=0;

 for(i=0;i<d1;i++)
 {
   for(j=0;j<d2;j++)
   {
     if(A1[i]==A2[j]) D[i+1][j+1]=D[i][j]+1;
     else
     {                 
          if(D[i][j+1]>D[i+1][j]) D[i+1][j+1]=D[i][j+1];
          else D[i+1][j+1] = D[i+1][j];
     }
   }
 }         

// wynik jest w D[d1,d2]

  for(i=0;i<=d1;i++)
 {
    printf("wiersz %d: ",i);
    for(j=0;j<=d2;j++)  printf(" %d  ",D[i][j]); 
    printf("\n");    
 }
 i=d1;
 j=d2;
 
 Stos s;
 
 while((i>0) && (j>0))
 {
   if(A1[i-1]==A2[j-1])
   {
     s.Put(A1[i-1]);
     i--;
     j--;  // {przejscie do stanu (i-1,j-1), bo z niego korzystalismy}
   } 
   else
   {
         if(D[i][j+1]>D[i+1][j]) i--;//   {przejscie do stanu (i-1,j)}
         else j--; // {przejscie do stanu (i,j-1)}
    }
 }

 //{literki kolejno zdejmowane ze stosu tworza najw.wsp.podciag;
 // gdy stos jest pusty, to podciag jest pusty}
  
 printf("dlugosc NWP: %d\nNWP: ",D[d1][d2]);
 
 while(!s.Empty()) printf("%c",s.Pop());
 printf("\n");
 system("pause");
 return 1; 

}