Common sub-string in alphabetic order

Question

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;
}

Allocating close to 1 MiB of working memory in `chart` seems like it should be overkill; are you sure that's sensible? Could you call the function reliably on multiple different substrings? — Jonathan Leffler, Nov 22 '18 at 14:28
Incidentally, see [Why `gets()` is too dangerous to be used — ever!](https://stackoverflow.com/questions/1694036/why-is-the-gets-function-so-dangerous-that-it-should-not-be-used) — Jonathan Leffler, Nov 22 '18 at 14:29
If the code works, why is there a question? It doesn't work correctly — it doesn't produce the correct result. You don't scan through possible results looking for the first in alphabetic order. I don't understand how your 2D array works; I'm not sure I want to since I think it is fundamentally wrong to allocate O(N²) space for this problem. However, maybe the trouble is that you don't know how to do dynamic memory allocation with `malloc()` (and how to release it with `free()`), in which case, there is an excuse for what is otherwise serious overkill. — Jonathan Leffler, Nov 22 '18 at 14:39
SO is not a good debugger. https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — , Nov 22 '18 at 16:50

score 0 · Accepted Answer · answered Nov 22 '18 at 23:26

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 = %s\n", 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;
}

Common sub-string in alphabetic order

1 Answers1