Efficient algorithm to search for matching substrings longer than 14 characters of a text inside another text

algorithm, c, c++, string

Solution

Stand back, I'm gonna live-code:

void match_substring(const char *a, const char *b, int n) // n=15 in your case
{
    int alen = strlen(a); // I'll leave all the null-checking and buffer-overrun business as an exercise to the reader
    int blen = strlen(b);
    for (int i=0; i<alen; i++) {
        for (int j=0; j<blen; j++) {
            for (int k; (i+k<alen) && (j+k<blen) && a[i+k]==b[i+k]; k++);
            if (k >= n)
                printf("match from (%d:%d) for %d bytes\n", i, j, k);
        }
    }
}

Problem

I've got a long text (about 5 MB filesize) and another text called pattern (around 2000 characters). The task is to find matching parts from a genom-pattern which are 15 characters or longer in the long text. example: long text: ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT AND MUCH LONGER pattern: ACGGTATTGAC AAAACCCCGGGGTTTTA TGTTCCCAG I'm looking for an efficient (and easy to understand and implement) algorithm. A bonus would be a way to implement this with just char-arrays in C++ if thats possible at all.

Original source