the KMP algorithm for indexing sub-strings.

kmp.c

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


int *build_next(const char *pat, int pat_len)
{ int i;
    int *next = (int *)malloc(pat_len * sizeof(*next));

    next[0] = -1;
    for (i = 1; i < pat_len; i++) {
        int next_middle = next[i-1];
        while (next_middle >= 0) {
            if (pat[i-1] == pat[next_middle]) {
                break;
            } else {
                next_middle = pat[next_middle];
            }
        }
        next[i] = next_middle + 1;
    }

    return next;
}

int KMP_Search(const char *src, const char *pat, const int *next)
{
    int src_len = strlen(src);
    int pat_len = strlen(pat);

    int i,j;

    i=0;
    j=0;
    while (i<src_len && j<pat_len) {
        if (j==-1 || src[i] == pat[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j >= pat_len) {
        return i - pat_len;
    } 

    return -1;
}

int KMP(const char *src, const char *pat)
{
    int *next = build_next(pat, strlen(pat));
    int ret = KMP_Search(src, pat, next);
    free(next);

    return ret;
}

int main(int argc, const char *argv[])
{
    
    const char *src = "aaaaaaaaaaaaaaacaaaaaaaaaaaaaaab";
    const char *pat = "aaaab";

    printf("%d\n", KMP(src, pat));
    return 0;
}