Longest common sub-string of two given strings using suffix array

Write a program to find the longest common sub-string of two given strings.

For example, given two strings, "philologist" and "lollipop", "lol" is the LCS.
Here we use suffix arrays.

The approach:-

1. Create a char pointer array pointing each of the character in the first string. Similarly create another array for second string



2. Re-order the pointers in the arrays, using qsort, so that the string pointed to by them are in sorted order.



3. Finally use "merge two sorted linked list" kind of technique to compare the strings and look for the match (full or partially) and keep track of the longest one during iteration.

The solution:-

#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <string.h>

// Used for quicksort
int compare(const void *a, const void *b)
{
    const char* a1 = *(const char**)a;
    const char* b1 = *(const char**)b;
    return strcmp(a1,b1);
}

//create a pointer list to each of the characters in the input.
char** formSuffixList(char* input)
{
    char ** sub_str = (char **)malloc(strlen(input) * sizeof(char*));
    char *tmp = input;
    int i = 0;
    while (*tmp != '\0' ) {
        sub_str[i] = tmp;
        tmp++; i++;
    }
    return sub_str;
}

//returns position where the change is. And the sign tells which is higher value.
int matchstr(const char *a, const char *b)
{
    int i=0;
    while(*a == *b) {
        if ( *a == '\0' || *b == '\0' )
           break;
        i++;a++;b++;
    }
    i++;
    if (*a == '\0')
        return i;
    if (*b == '\0')
        return -i;

    if (*a > *b)
        return i;
    else
        return -i;
}

int main()
{
    int c1, c2;

    char* str1 = "madmandogcat";
    char* str2 = "xyzdmanzyandogcio";

    char** _array1 =  formSuffixList(str1);
    char** _array2 =  formSuffixList(str2);

    c1 = strlen(str1);
    c2 = strlen(str2);
    qsort(_array1,c1, sizeof(char*),compare);
    qsort(_array2,c2, sizeof(char*),compare);

    int best = 0;
    char *lcs;
    c1--;c2--;
    while ( (c1>=0) && (c2>=0)) {
        int n = matchstr(_array1 [c1],_array2 [c2]);
        if ( abs(n)-1 > best) {
            best  = abs(n)-1;
            lcs = _array1 [c1];
        }
        if (n > 0)
            c1--;
        else
            c2--;
    }
    char* res = (char*)malloc(best+1);
    memcpy(res,lcs,best);
    res[best] = '\0';
    printf ("LCS len: %d and string: %s\n",best, res);
    delete res;
    delete _array1;
    delete _array2;
}

Output:-

LCS len: 6 and string: andogc