28. 实现 strStr()_kmp算法

28. 实现 strStr()的kmp算法改进

void nex(char *s, int *next)
{
    next[0] = 0;
    int now = 0, x = 1;
    while (x < strlen(s))
    {
        if (s[now] == s[x])
        {
            now += 1;
            next[x] = now;
            x += 1;
        }
        else if (now)
        {
            now = next[now - 1];
        }
        else
        {
            next[x] = 0;
            x += 1;
        }
    }
}


int kmp(char *s, char *p)
{
    int *next = NULL;
    next = (int *)malloc(sizeof(int) * strlen(p));
    nex(p, next);
    int now = 0, px = 0;
    while (now < strlen(s))
    {
        if (p[px] == s[now])
        {
            px += 1;
            now += 1;
        }
        else if (px)
            px = next[px - 1];
        else
            now += 1;
        if (px == strlen(p))
        {
            return now-px;
        }
    }
    return -1;
}
int strStr(char * haystack, char * needle){
if(!strlen(needle))
return 0;
return kmp(haystack,needle);
}