KMP for comparison

For comparison with the previous post, this is how KMP would look like:

static void kmp_search(char * key, char * buffer)
{
    unsigned long n = strlen(buffer);
    unsigned long m = strlen(key);
    unsigned long ba[m];
    ba[0] = 0;
    for (unsigned long i = 1; i < m; ++i) {
        unsigned long b = ba[i-1];
        while (b > 0 && key[i] != key[b])
            b = ba[b-1];
        ba[i] = (key[i] == key[b]) ? b + 1 : 0;
    }
    unsigned long i, j; i = j = 0;
    while (i < n - m + j) {
        while (buffer[i] == key[j] && j < m) {
            ++i; ++j;
        }
        if (j == m) printf("%lu\n", i - m);
        if (j == 0) ++i;
        else j = ba[j-1];
    }
}

This algorithm is doing essentially the same thing as the border-array based algorithm, but the two loops look very different and you need to get both of the right. The previous algorithm also has two loops, but they are doing the same thing, so if you get one of the right you will very easily get the other right as well.

Author: Thomas Mailund

My name is Thomas Mailund and I am a research associate professor at the Bioinformatics Research Center, Uni Aarhus. Before this I did a postdoc at the Dept of Statistics, Uni Oxford, and got my PhD from the Dept of Computer Science, Uni Aarhus.

Leave a Reply