实现strStr

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ReleaseNext(p) if(p) free(p)

int* buildNext(char* patten, int n) {
    int* next = (int*)malloc(n * sizeof(int));
    next[0] = -1;
    int j = -1;    
    for(int i = 0; i < n - 1; i++) {
        for (; j >= 0 && patten[j] != patten[i]; j = next[j]); 
        next[i + 1] = ++j;
    }
    return next;
}

int kmp(char* str, int n, char* patten, int m, int* next) {
    int j = 0;
    for(int i = 0; i < n; i++) {
        for (; j >= 0 && patten[j] != str[i]; j = next[j]);
        if(++j < m)
            continue;

        ReleaseNext(next);
        return i - m + 1;
    }
    ReleaseNext(next);
    return -1;
}

int strStr(char* str, char* patten) {
    if(!str || !patten)
        return -1;

    int m = strlen(patten);
    if(m == 0) 
        return -1;

    int n = strlen(str);
    if(n == 0)
        return -1;

    int* next = buildNext(patten, m);
    int res = -1;
    next ? res = kmp(str, n, patten, m, next) : res = -1;
    return res;
}

int main() {
    char s1[] = "hello";
    char s2[] = "ll";
    printf("%d\n", strStr(s1, s2));
    return 0;
}