Mam pewne zadanie. Jest ono mniej więcej takie:
1. Mam stworzyć 2 tablice dla których zostaną załadowane od użytkownika 2 wyrazy.
2. W tych 2 słowach mam znaleźć najdłuższe podsłowo, które jest wspólne dla obu łańcuchów...
Może dam przykład:
Dla danych wejściowych: abaab bbbaaa
poprawną odpowiedzią jest: 3
Najdłuższym wspólnym podsłowem powyższych słów jest słowo baa.
W oparciu o: ... ng_problem
starałem się to zaimplementować to w C. Niby się udało (dla tego konkretnego przykładu) wyświetla dobrze ale:
-nie jest to zgodne z tym pseudokodem z wikipedii a co za tym idzie sądzę, że mój kod nie jest optymalny (pomijając już zasady programowania strukturalnego, według których nie powinienem był chyba tworzyć takiej dłuuuuugiej funkcji)
-dla przykładu z wikipedii czyli ABAB oraz BABA w których mamy dwa wspólne podsłowa -ABA oraz BAB wyśiwetla oczywiście tylko pierwsze z nich (to przez to goto które chyba też nie jest najszczęśliwsze i dodatkowo zaciemnia kod) myślałem nad modyfikacją tego ale powiem szczerze, że niezbyt widzę sens tego...
W związku z tym:
Czy mógłby mi ktoś podpowiedzieć jak ten kod naprawić/zoptymalizować bądź wkleić własną implementację tego, która będę mógł przeanalizować?
Dzięki wielkie.
Oto kod(postarałem się go trochę opisać by chociaż trochę był czytelniejszy):
Kod: Zaznacz cały
void LCSuff(char*slowo1,char*slowo2)
{
int size1,size2,i,j,longer;
size1=strlen(slowo1);size2=strlen(slowo2);
int tab[size1][size2];
/*Stworzenie tablicy do ktorej zostanie zapisany podciag*/
if(size1>=size2)longer=size1;
else longer=size2;
char substring[longer];
/***************************************************/
/*Tablica "zero-jedynek"*/
for(i=0;i<size1;i++)
{
for(j=0;j<size2;j++)
{
if(slowo1[i]==slowo2[j])
{
tab[i][j]=1;
}
else tab[i][j]=0;
}
}
/****************************************************/
/*Znalezienie dlugosci tego lancucha*/
int p=0,x,k,m,g=0;
for(i=0;i<size1;i++)
{
x=0;
for(j=0;j<size2;j++)
{
x=0;
if(tab[i][j]==1)
{
k=i;m=j;
while((tab[k][m]==1)&&(k<size1)&&(m<size2))
{
k++;m++;x++;
if(p<x)p=x;
}
}
}
}
/******************************************/
/*Znalezienie indeksu w tablicy slowo1 od ktorego nalezy czytac podslowo*/
k=0;m=0;
int z,l=0,y;
p--;y=p;p++;
for(i=0;i<size1;i++)
{
for(j=0;j<size2;j++)
{
if(tab[i][j]==1)
{
k=i;m=j;z=i;
while((tab[k][m]==1)&&(k<size1)&&(m<size2))
{
l=k;
k++;m++;
}
if((l-z)==y) goto label;
}
}
}
label:
/*Koopiowanie podslowa do tablicy*/
j=0;
for(i=z;i<=l;i++)
{
substring[j]=slowo1[i];
j++;
}
printf("Najdluzsze wspolne podslowo to: ");
puts(substring);//dla (abaab i bbbaaa) dziala ale nie dla ABAB i BABA
};