KMP string matching

 
 
#include<iostream>

void preProcess(int *kmpNext, 
                const char *pattern) {
    int j = -1;
    int i = 0;
    kmpNext[i] = j;
    int len = strlen(pattern);

    while(i<len) {
        while(j >=0 && pattern[i] != pattern[j]) 
            j=kmpNext[j];    

        ++i;++j;
        kmpNext[i] = j;

        if (pattern[i] == pattern[j])
            kmpNext[i] = kmpNext[j];
        else
            kmpNext[i] = j;
    }
    
    return;    
}

void match(const char *str,
           const char *pattern,
           const int *pre) {
    int m = 0;
    int i = 0;
    int len = strlen(str);
    
    while(m+i < len) {
        if(str[m+i] == pattern[i]) {
            i++;

            if(i == strlen(pattern)) {
                std::cout << "Match found at index: " 
                          << m << std::endl;
            }
        }
        else {
            m = m + i - pre[i];
            if(i > 0) {
                i = pre[i];
            }
        }
    }    
    return;
}

void KMP() {
    char String [] = "abcabcabdewqabcabd";
    char pattern [] = "abcabd";
    
    int *pre = new int [strlen(pattern)+1];
    memset(pre, 0, (strlen(pattern)+1) * sizeof(int));
    
    /* Preprocess the table */
    preProcess(pre, pattern);

    for(int i =0; i<strlen(pattern)+1; ++i)
        std::cout << pre[i] << " ";
    std::cout << std::endl;

    /* Match the string */
    match(String, pattern, pre);

    delete pre;
    return;
}

int main() {
    KMP();
    return 0;
}