How to Find Longest Common Substring Using C++

How to find Longest Common Substring using C++

Here is an excellent article on finding all common substrings efficiently, with examples in C. This may be overkill if you need just the longest, but it may be easier to understand than the general articles about suffix trees.

Finding the longest common word in two strings in C Language?

This example prints the longest substring given two input strings.

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

int *lcommon(char *str1, char *str2) {
    int strlen1 = (unsigned) strlen(str1);
    int strlen2 = (unsigned) strlen(str2);
    int i, j, k;
    int longest = 0;
    int **ptr = malloc(2 * sizeof(int *));
    static int *ret;
    ret = calloc((unsigned) strlen1 + 1, sizeof(int));
    for (i = 0; i < 2; i++)
        ptr[i] = calloc((unsigned) strlen2, sizeof(int));

    k = 0;
    for (i = 0; i < strlen1; i++) {
        memcpy(ptr[0], ptr[1], strlen2 * sizeof(int));
        for (j = 0; j < strlen2; j++) {
            if (str1[i] == str2[j]) {
                if (i == 0 || j == 0) {
                    ptr[1][j] = 1;
                } else {
                    ptr[1][j] = ptr[0][j-1] + 1;
                }
                if (ptr[1][j] > longest) {
                    longest = ptr[1][j];
                    k = 0;
                    ret[k++] = longest;
                }
                if (ptr[1][j] == longest) {
                    ret[k++] = i;
                    ret[k] = -1;
                }
            } else {
                ptr[1][j] = 0;
            }
        }
    }
    for (i = 0; i < 2; i++)
        free(ptr[i]);
    free(ptr);
    ret[0] = longest;
    return ret;
}

int main(int argc, char *argv[]) {
    int i, longest, *ret;

    if (argc != 3) {
        printf("usage: longest-common-substring string1 string2\n");
        exit(1);
    }

    ret = lcommon(argv[1], argv[2]);
    if ((longest = ret[0]) == 0) {
        printf("There is no common substring\n");
        exit(2);
    }

    i = 0;
    while (ret[++i] != -1) {
        printf("%.*s\n", longest, &argv[1][ret[i]-longest+1]);
    }

    exit(0);
}

Test

$ ./a.out computerprogramming javaprogrammer
programm

You can read more about the problem here.

You can also use an interactive program where you write the strings in the console:

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

int *lcommon(char *str1, char *str2) {
    int strlen1 = (unsigned) strlen(str1);
    int strlen2 = (unsigned) strlen(str2);
    int i, j, k;
    int longest = 0;
    int **ptr = malloc(2 * sizeof(int *));
    static int *ret;
    ret = calloc((unsigned) strlen1 + 1, sizeof(int));
    for (i = 0; i < 2; i++)
        ptr[i] = calloc((unsigned) strlen2, sizeof(int));

    k = 0;
    for (i = 0; i < strlen1; i++) {
        memcpy(ptr[0], ptr[1], strlen2 * sizeof(int));
        for (j = 0; j < strlen2; j++) {
            if (str1[i] == str2[j]) {
                if (i == 0 || j == 0) {
                    ptr[1][j] = 1;
                } else {
                    ptr[1][j] = ptr[0][j - 1] + 1;
                }
                if (ptr[1][j] > longest) {
                    longest = ptr[1][j];
                    k = 0;
                    ret[k++] = longest;
                }
                if (ptr[1][j] == longest) {
                    ret[k++] = i;
                    ret[k] = -1;
                }
            } else {
                ptr[1][j] = 0;
            }
        }
    }
    for (i = 0; i < 2; i++)
        free(ptr[i]);
    free(ptr);
    ret[0] = longest;
    return ret;
}

int main(int argc, char *argv[]) {
    int i, longest, *ret;

    if (argc != 3) {
        //printf("usage: longest-common-substring string1 string2\n");

        char s[20], t[20];
        printf("Type in a string s.\n");
        fgets(s, 20, stdin);
        printf("Type in a string t.\n");
        fgets(t, 20, stdin);

        ret = lcommon(s, t);
        if ((longest = ret[0]) == 0) {
            printf("There is no common substring\n");
            exit(2);
        }

        i = 0;
        while (ret[++i] != -1) {
            printf("%.*s\n", longest, &s[ret[i] - longest + 1]);
        }

        //printf("The result of comparison=%d\n", strcmp(s, t));

        exit(0);
    } else { }
    ret = lcommon(argv[1], argv[2]);
    if ((longest = ret[0]) == 0) {
        printf("There is no common substring\n");
        exit(2);
    }

    i = 0;
    while (ret[++i] != -1) {
        printf("%.*s\n", longest, &argv[1][ret[i] - longest + 1]);
    }
    exit(0);
}

Test

Type in a string s.
string1
Type in a string t.
string2
string

Related Topics