Qfyilyi

I'm trying to write a code that gets two strings of maximum length 1000 uppercase characters and then prints their longest common sub-string BUT if there were more than one sub-strings of the maximum length the output must be the sub-string that comes first in the alphabetic order .
example:
input:DEFTABC,DEFHABC
output:ABC
Here's my code that I wrote but the problem of this code is that for above inputs it gives "DEF" instead of "ABC",please help me correct my code.

#include<stdio.h>

#include<string.h>

int chart[1002][1002];

void commonsubstring(char str1,char str2,int m,int n){

int len=0;

int row,col,i,j;

for(i=0;i<=m;i++){

    for(j=0;j<=n;j++){

        if(i==0 || j==0){

          chart[i][j]=0;

        }

        else if(str1[i-1]==str2[j-1]){

            chart[i][j]=chart[i-1][j-1]+1;

            if(len<chart[i][j]){

                len=chart[i][j];

                row=i;

                col=j;

            }

        }

        else{

            chart[i][j]=0;

        }

    }

}

if(len==0){

    return;

}

char result[1001];

while(chart[row][col]!=0){

    result[--len]=str1[row-1];

    row--;

    col--;

}

puts(result);

}

int main(){

char str1[1001],str2[1001];

gets(str1);

gets(str2);

int m,n;

m=strlen(str1);

n=strlen(str2);

commonsubstring(str1,str2,m,n);

return 0;

}

Use standard string functions to make the code less convoluted. If for some reason strcmp, strstr etc. are not available, then you can make your own functions.

You don't need an array of 1000 strings of size 1000. Just get the shorter string and find all its sub-strings. If the sub-string is found in the larger string, then make that your result. If result already exists, make sure that new match is longer than the existing result, and is lower in the alphabetic order. Example:

#include<stdio.h>

#include<stdlib.h>

#include<string.h>



void common(char* m, char* n)

{

    char *a = m;

    char *b = n;

    if(strlen(a) > strlen(b))

    {

        //make sure the shorter string is used first

        a = n;

        b = m;

    }



    int len = strlen(a);



    char *substr = malloc(len + 1);

    char *result = malloc(len + 1);

    result[0] = 0;



    for(int beg = 0; beg < len - 1; beg++)

    {

        for(int end = beg + 1; end < len; end++)

        {

            //find all substrings in "a":

            strncpy(substr, a + beg, end - beg + 1);

            substr[end - beg + 1] = 0;



            //see if substring is in "b":

            if(strstr(b, substr))

            {

                //we want the longest common substring

                if(strlen(substr) < strlen(result))

                    continue;



                //sort by alphabetic order

                if(strlen(substr) == strlen(result))

                    if(strcmp(substr, result) > 0)

                        continue;



                strcpy(result, substr);

            }

        }

    }



    printf("result = %sn", result);



    free(substr);

    free(result);

}



int main(void)

{

    char str1[1001], str2[1001];

    fgets(str1, sizeof(str1), stdin);

    fgets(str2, sizeof(str2), stdin);

    common(str1, str2);

    return 0;

}