KMP

Reference:

1. wikipedia:Knuth–Morris–Pratt algorithm
2. Matrix67: KMP算法详解
3. 演算法筆記: String Matching
4. 喜刷刷: Implement strStr() - KMP解法

A string: abababaabab
B string: ababacb

m: length of A string
n: length of B string

1. do preProcess of B sting to get a array of preProcess(need additional space n) array of preProcess: [-1,-1,0,1,2,-1,-1]
2. check if B is sub-string of A by array of B's preProcess

KMP's time complexity: O(m+n)

//s: string
//n: length of s
//p: array of Pre-Procesing
void KMPpreProcessing(const char *s, int n, int *p)
{
    int j;

    memset(p, -1, sizeof(int)*n);
    j = -1;

    for(int i =1; i<n; i++) {
        while(j>-1 && s[i]!=s[j+1])
            j = p[j];
        if(s[i]==s[j+1])
            j++;
        p[i] = j;
    }
}

int strStr(const char *s1, const char *s2)
{
    int m, n, j, *p;

    if(s1==NULL || s2==NULL) return -1;
    else if(!*s2 || (!*s1 && !*s2)) return 0;
    else if(!*s1) return -1;


    m = strlen(s1);
    n = strlen(s2);
    p = (int*)malloc(sizeof(int)*n);
    j = -1;

    KMPpreProcessing(s2, n, p);

    for(int i=0; i<m; i++) {
        while(j>-1 && s1[i]!=s2[j+1])
            j = p[j];
        if(s1[i] == s2[j+1])
            j++;
        if(j == n-1)
            return (i-n+1);
    }

    free(p);

    return -1;
}