Nën-vargu i përbashkët me gjatësi maksimale

[JACK FOLLA]

Peshendetje.
Pashe se ne kete forum ka njerz te afte ne programim,una kam nevoje per nje ndihme ne gjuhen C.
Duhet te ndertoj nje librari qe te kete nj fuksion qe ka si parametra 2 stringa dhe vendos kush eshte nenstringa e perbashket me gjatesi maksimale.(p.sh. maria eshte nenstringa me gjatesi maksimale te perbashket te stringave "marinaio" e "malaria".)
Faleminderit paraprakisht edhe per ndonje keshille per ndonje sit ku mund te gjej material per Gjuhen C.

[qoska]

jack folla tani ti do tegjesh sa karaktere te perbashketa kane keto stringa apo do te gjesh stringen me te gjate te perbashket.
Pasi nga shembulli qe ke dhene ti stringa me e gjate e perbashket eshte "ria".

Sqaroje me mire qe te te ndihmojme me shume.

Per sa i perket krijimit te librarise mjafton qe te mos kesh deklarim te funksionit si static dhe ta kompilosh me kushtin -shared kur perdor gcc si psh:
gcc -o foo.so foo.c -shared.

dhe per ta perdorur kete librari ne nje projekt nqs libraria eshte ne te njejten direktori me file qe do kompilosh majfton:

gcc -o prog prog.c -I. -lfoo.

Ne windows duhet te besh dicka me shume pasi duhet ti besh "export" funksionit dhe varet nga menyra qe zgjedh per kalimin e variblave ne stack etj,,.

Gjithsesi nqs do nje sheembull me kod, sqarohu me mire se cfare kerkon nga programi sic te thashe me lart.
TUNG!

[JACK FOLLA]

Ne shembullin qe kam dhene stringa e perbashket eshte siç thashe maria dhe jo ria sepse kemi edhe ma tek fjalet marinaio e malaria.
une kam provuar dhe kam bere kete kod por nuk me jep rezultatin e duhur.

#include

#define N 1000

main(int argc, char *argv[])
{
int i,j,t;
char a[N], *p=argv[1];
for(i=0;i if ((t=getchar()) == EOF)
break;
a[i] = 0;
for(i=0;a[i] != 0; i++)
{
for (j = 0; p[j] != 0; j++)
if (a[i+j] != p[j])
break;
if (p[j] == 0)
printf("%d", i);
}
printf("\n");
}


Sidoqofte faleminderit per interesimin.

[Clauss]

1 nenstring te perbashket maximal , me duket se del "ari"
me duket se ne fillim duhet te besh define cfare nenkupton me "nenstring" me "maximal" dhe me "te perbashket"?

1) shkronja te njejta ne te njejten seri ne te dy fjalet?
2) shkronja te njejte me cfaredolloj serie ne te dy fjalet?
3) ndonje tjeter?

une skuptoj si nenshtring i perbashket i:
m - a - l - a - r - i - a
m - a - r - i - n - a - i - o

eshte "maria" ?
mbase e kam keqkuptuar, por sidoqofte me duket se kuptimi i "nenstring" eshte ndryshe.

[EdiR]

Me duket se nuk ke kuptuar se cfare te kerkohet ty dhe keshtu qe nuk ke shpjeguar qarte se si mund te te ndihmojme.
Une nuk jam ekspert ne C po jam i sigurt qe eshte si Java dhe si gjithe te tjerat. Bashkohem me mendimin mesiper qe i vetmi nenstring i perbashket eshe "ari" ndersa ajo qe thua ti eshte me gjithe characters qe keto dy fjale kane te perbashket mund te formosh "maria".
Nga pervoja ime e programimit nuk duhet te perdoresh break me shume se njehere kur do te dalesh nga ekzekutimi i kodit.
Se dyti, si zgjedh perseritjet e te njejtit char si p.sh 'a'?
Kuket sikur ti ke inicilizuar array of char por nuk jam i sigurt se kur futet karakteri i gjetur ne char array.
Ne pseudoKod do te ishte dicka e till.
1) gjej stringun me te gjate nese njeri eshte ashtu.
2) per secilin nga char e stringut me te gjate shiko nese nje nje char i tille eshte prezent ne stringun tjeter.
3) nese eshte shto ate ne nje variable array quaje si te duash : theResult [i]=thechar.
4) kur te mbarosh me te gjithe char e stringut me te gjate do te kesh cfare te duhet ne rezultat dhe mund te printosh.
Keshtu e kuptoj une dhe nese do te dija pak me shume c syntacs do te kish ndihuar me shume.
Perpiqu te shpjegosh veten pak me mire dhe po e pe keq dergo nje mesazh tek edispace se jam i sigurt qe ka punuar me c dhe do te beje c'eshte e mundur te te ndihmoje.
Kalofsh mire dhe shpresoj te zgjithes sa me shpejt.
Edi

[IlirDeda]

Kuptimi i nenstring varet nga percaktimi. Disa mund ta percaktojne sic e dha Jack Folla, disa mund ta percaktojne sic e japin EdiR, Clauss dhe qoska.

Algoritmet ne te dyja rastet nuk jane te lehte per tu shkruar. Varianti qe kerkon Jack me duket pak me i veshtire.

Per te realizuar detyren e Jack une vendosa te implementoj algoritmin e pare te pershkruar ne kete faqe:
http://www2.toki.or.id/book/AlgDesig...00000000000000

Kodi vijon me poshte:

#include <stdio.h>
#include <string.h>
#include <malloc.h>

void ReverseInPlace(char* string) {
    int len = strlen(string);
    int i;
    for(i = 0; i < len/2; i++) {
        char temp = string[i];
        string[i] = string[len - i -1];
        string[len-i -1] = temp;
    }
}

/* Special Get function that returns 0 if the row or column index are negative */
int GetElement(int* matrix, int numColumns, int i, int j) {
    if(i<0 || j<0) {
        return 0;
    } else {
        return matrix[i*numColumns + j];
    }
}

int Max(int n1, int n2) {
    if(n1>n2) {
        return n1;
    } else {
        return n2;
    }
}

int Max3(int n1, int n2, int n3) {
    return Max(Max(n1, n2), n3);
}


void FindLongestCommonString(char* str1, char* str2, char** result) {
    int numRows = strlen(str1);
    int numColumns = strlen(str2);
    int* matrix = (int*)malloc(numRows * numColumns * sizeof(int));
    int i, j;
    for(i = 0; i < numRows; i++) {
        for(j = 0; j < numColumns; j++) {
            if(str1[i]==str2[j]) {
                matrix[i*numColumns + j] = Max3(GetElement(matrix, numColumns, i-1, j-1) + 1,
                                             GetElement(matrix, numColumns, i-1, j),
                                             GetElement(matrix, numColumns, i, j-1));
            } else {
                matrix[i*numColumns + j] = Max( GetElement(matrix, numColumns, i-1, j),
                                             GetElement(matrix, numColumns, i, j-1));
            }
        }
    }

    /* Note: Length of the longest common string is matrix[numColumns * numRows - 1] */
    int lenLCM = matrix[numColumns * numRows - 1];

    *result = (char*) malloc((lenLCM +1) * sizeof(char));

    /* Backtrack to find the string */
    i = numRows - 1;
    j = numColumns - 1;
    int k = 0;
    while (k < lenLCM) {
        if (GetElement(matrix, numColumns, i, j) ==
                   GetElement(matrix, numColumns, i-1, j)) {
            i--;
        } else if (GetElement(matrix, numColumns, i, j) ==
                   GetElement(matrix, numColumns, i, j-1)) {
            j--;
        } else {   /* str1[i] == str2[j] */
            (*result)[k] = str1[i];
            i--;
            j--;
            k++;
        } 
    }

    (*result)[lenLCM] = 0;
    free(matrix);
    ReverseInPlace(*result);
}

int main(int argc, char* argv[])
{
    if(argc!=3) {
        printf("Usage: %s <string1> <string2>\n", argv[0]);
        return 1;
    }

    char* result;
    FindLongestCommonString(argv[1], argv[2], &result);
    printf("The Longest Common String between %s and %s is:\n\t%s\n", argv[1], argv[2], result);
    free(result);

    return 0;
} 

[edspace]

Më poshtë ke dhe zgjidhjen time të problemit.

Algoritmi është i thjeshtë për të kuptuar. Nesër do shkruaj disa komente për kodin dhe mund të përmirësojmë algoritmin.

1. Marrim dy fjalë, f1 dhe f2.
f1 = marinaio
f1 = malaria

2. Filtrojmë vetëm shkronjat e përbashkëta tek të dyja fjalët.
f1 = mariai
f2 = maaria

3. Gjejmë vargun më të madh të f1 që i përshtatet f2.
rez1 = maria

4. Gjejmë vargun më të madh të f2 që i përshtatet f1.
rez2 = aria

5. Vargu me gjatësi maksimale është rezultati më i gjatë.
rez_maks = rez1 = maria


Ja dhe kodi në C, përpiluar me gcc 4.3.2.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <errno.h> 

void strfiltro(char ** varg, char * filter); 
void gjej_varg_perbashket(char * f1, char * f2, char ** rez); 

int main(int argc, char * argv[]) 
{ 
    char * f1, * f2, * rez1, * rez2, * rez_maks; 

    if (argc != 3) { 
        printf("Programi kerkon 2 argumenta\n"); 
        return 1; 
    } 
    
    f1 = (char *)malloc((strlen(argv[1])+1) * sizeof(char)); 
    f2 = (char *)malloc((strlen(argv[2])+1) * sizeof(char));

    if (f1 == NULL || f2 == NULL) { 
        printf("Kompjuteri nuk ka memorje te mjaftueshme\n"); 
        return 1; 
    } 
    strcpy(f1, argv[1]); 
    strcpy(f2, argv[2]); 
     
    strfiltro(&f1, f2); 
    strfiltro(&f2, f1); 

    gjej_varg_perbashket(f1, f2, &rez1); 
    gjej_varg_perbashket(f2, f1, &rez2); 
    if (errno != 0) return 1; 
     
    if (strlen(rez1) >= strlen(rez2)) { 
        rez_maks = rez1; 
    } else { 
        rez_maks = rez2; 
    } 

    if (strlen(rez_maks) == 0) { 
        printf("Fjalet nuk kane asnje varg te perbashket\n"); 
    } else { 
        printf("Vargu me i madh i perbashket: %s\n", rez_maks); 
    } 
    
    system("pause");
    return 0; 
} 

void strfiltro(char ** varg, char * filter) 
{ 
    int gjatesia, j = 0, i;
    char * varg_i_filtruar;
    
    gjatesia = strlen(*varg); 
    varg_i_filtruar = (char *)malloc((gjatesia + 1) * sizeof(char)); 

    if (varg_i_filtruar == NULL) { 
        printf("Kompjuteri nuk ka memorje te mjaftueshme\n"); 
        return; 
    } 
    memset(varg_i_filtruar, '\0', gjatesia  + 1); 

    for (i = 0; i < gjatesia; i++) { 
        if (strchr(filter, (*varg)[i]) != NULL) { 
            varg_i_filtruar[j++] = (*varg)[i]; 
        } 
    } 
     
    free(*varg); 
    *varg = varg_i_filtruar; 
} 

void gjej_varg_perbashket(char * f1, char * f2, char ** rez) 
{ 
    int f1_gjat, f2_gjat, i, j, k, f12i; 
    char * f12_maks, * f12; 

    f1_gjat = strlen(f1); 
    f2_gjat = strlen(f2); 

    f12_maks = (char *)malloc((f1_gjat + 1) * sizeof(char)); 
    f12 = (char *)malloc((f1_gjat + 1)  * sizeof(char)); 

    if (f12_maks == NULL || f12 == NULL) { 
        printf("Kompjuteri nuk ka memorje te mjaftueshme\n"); 
        errno = ENOMEM; 
        return; 
    }
     
    memset(f12_maks, '\0', f1_gjat + 1); 
    memset(f12, '\0', f1_gjat + 1);

    for (i = 0; i < f1_gjat; i++) { 
        for (j = i, k = 0, f12i = 0; j < f1_gjat; j++) { 
            for ( ; k < f2_gjat; k++) { 
                if (f1[j] == f2[k]) { 
                    f12[f12i++] = f1[j]; 
                    k++; 
                    break; 
                } 
            } 
        } 

        if (strlen(f12) > strlen(f12_maks)) { 
            memset(f12_maks, '\0', f1_gjat + 1); 
            strcpy(f12_maks, f12); 
            if (strlen(f12_maks) >= f1_gjat - i) { 
                break; 
            } 
        } 
        memset(f12, '\0', f1_gjat + 1); 
    } 

    free(f12); 
    *rez = f12_maks; 
} 

[JACK FOLLA]

Edi faleminderit per interesimin,ideja dhe shqyrtimi i problemit eshte shume e sakte dhe e zgjuar por kur kompilova programin tend me Visual C++,me jep shume gabime.
Gjithsesi faleminderit,une do ye vazhdoj te prepiqem,por nese dikush di ndonje sit me algoritme te ketij lloji apo te ngjashem me ndihmon.
Gjithe te mirat.

[edspace]

Kodi me lart perpilohet edhe ne Visual Studio tani. Provoje dhe njehere. Arsyeja pse nuk te perpilohej me Visual C++ ishte sepse C-ja kerkon qe te gjitha variablat duhet te deklarohen qe ne krye, ndersa une i kisha deklaruar ne rreshtin ku ato perdoreshin per here te pare, si ne C++.
Megjithate kodi i meparshem perpilohej pa problem ne gcc 4.3.2. Merr perpiluesin Bloodshed Dev C++, eshte falas.

Ne lidhje me algoritmen e shprehur me lart, filtrimi i shkronjave te perbashketa eshte nje mendim i mire sepse thjeshton goxha kerkimin, cfaredo algoritmi te perdoresh.

Algoritmi im i pershtatjes se fjaleve punon pjeserisht, ndersa ajo qe ka shkruajtur Iliri punon per te gjitha rastet.

Psh:
programi "marianio" "malari" = "maria" => sakte
programi "uauhuai" "iaihiau" = "au" =/= "aha" => gabim

Aryeja per kete eshte se pasi behet filtrimi i shkronjave te perbashketa, programi ben krahasimin e shkronjave njera pas tjetres, kur ne fakt duhet te beje krahasimin e te gjithe kombinimeve te shkronjave.

Programi i Ilirit punon per te gjithe rastet besoj.

Megjithate, e kam vrare mendjen keto dite dhe mendoj se kam gjetur zgjidhjen per te permiresuar algoritmin tim qe te punoje per te gjitha rastet. Do gjej kohe keto dite per ta programuar dhe do te hedh perseri ne forum.

Nderkaq, perdor programin e Ilirit dhe, nqs do qe te punoje akoma me shpejt, filtroi fjalet me funksionin e programit tim, para se ti dergosh ne funksionin e Ilirit qe gjen fjalen me te gjate te perbashket.

[JACK FOLLA]

Edi e shkarkova kompilatorin,programi yt dhe i Ilirit me kompilohen pa gabime por dritarja e Dos-it me zhduket nuk e kuptoj pse sepse shoh qe ke perdorur edhe System (pause),
Une gjeta nje fuksion qe fuksionon shume mire ne te gjitha rastet.

#include    <stdio.h>
//#include    "simil.h"
#include    <string.h>

#define MAX_STR    256
#define MAX_LCS 256


void swap( unsigned **first, unsigned **second)
{
    unsigned *temp;
    temp=*first;
    *first=*second;
    *second=temp;
}
/* A function which returns how similar 2 strings are
   Assumes that both point to 2 valid null terminated array of chars.
   Returns the similarity between them.
*/
float simil( char *str1, char *str2)
{
    size_t len1=strlen(str1), len2=strlen(str2);
    float lenLCS;
    unsigned j, k, *previous, *next;
    if( len1==0 || len2==0)
        return 0;
    previous=(unsigned *)calloc( len1+1, sizeof(unsigned));
    next=(unsigned *)calloc( len1+1, sizeof(unsigned));
    for(j=0; j<len2; ++j){
        for(k=1; k<=len1; ++k)
            if( str1[k-1] == str2[j])
                next[k]=previous[k-1]+1;
            else next[k]=previous[k]>=next[k-1]?previous[k]:next[k-1];
        swap( &previous, &next);
    }
    lenLCS=(float)previous[len1];
    free(previous);
    free(next);
    return lenLCS/=len1;
}
/*    Returns a pointer to the Longest Common Sequence in str1 and str2
    Assumes str1 and str2 point to 2 null terminated array of char
*/

char *LCS( char *str1, char *str2)
{
  static char lcs[MAX_LCS];
  int i, r, c, len1=(int)strlen(str1), len2=(int)strlen(str2);
  unsigned **align;
  if( len1==0 || len2==0)
    return 0;
  align=(unsigned **)calloc( len2+1, sizeof(unsigned *));
  for( r=0; r<=len2; ++r)
      align[r]=(unsigned *)calloc( len1+1, sizeof(unsigned));
  for(r=1; r<=len2; ++r)
      for(c=1; c<=len1; ++c)
          if( str1[c-1] == str2[r-1])
              align[r][c]=align[r-1][c-1]+1;
          else align[r][c]=align[r-1][c]>=align[r][c-1]?align[r-1][c]:align[r][c-1];
  for(r=len2, c=len1,i=align[r][c], lcs[i]='\0';
      i>0 && r>0 && c>0; i=align[r][c]){
          if( align[r-1][c] ==i)
              --r;
          else if( align[r][c-1]==i)
              --c;
          else if(align[r-1][c-1]==i-1){
              lcs[i-1]=str2[--r];
              --c;
          }
  }
  for( r=len2;r>=0; --r)
      free( align[r]);
  free(align);
  return lcs;
}


int main( char *argv[], int argc)
{
    char    str1[MAX_STR], str2[MAX_STR], dump;
    printf("Type the 2 strings to compare.\nTo finish leave first string blank.\n");
    while(scanf("%[^\n]", str1) !=0 ){
        scanf("\n%[^\n]%c", str2, &dump);
        printf("\n\"%s\" and \"%s\" are %3.0f%% similar.\nOne of the longest common sequences is \"%s\".\n\n", str1, str2,
            simil(str1, str2)*100, LCS(str1, str2));
    }
    return 0;
} 

Faleminderit per gjitheçka,Edi je me te vertete shume i zoti do doja edhe une ta mesoja aq mire sity gjuhen C por nuk e di e gjej te veshtire.Ndoshta gaboj menyren e studimit,me jep ndonje keshille ose ushtrime se nga ana teorike e kam kuptuar disi.
Duke menduar rreth kodit ne kete librari qe duhet te krijoj duhet te perfshije edhe nje funksion tjeter perveç LCS qe e kam.

Konkretisht duhet te marre ne input 2 stringa dhe te stabilizoj nese stringa e pare eshte nenstringa e stringes se dyte,d.m.th. te gjithe karakteret e se pares shfaqen edhe tek e dyta ne te njejtin renditje edhe pse me karaktere te tjere ne brendesi. p.sh ('lira' eshte nje nenstringe e liberacione)