leecode之Implement strStr()

KMP算法的实现：

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

int strStr(char* haystack, char* needle) {
    if (haystack == NULL || needle == NULL)
        return -1;
    if (needle[0] == '')
        return 0;
    int lenPattern = strlen(needle);
    int lenHaystack = strlen(haystack);
    int *shift = (int *)malloc(sizeof(int) * lenPattern);
    int i;
    shift[0] = 0;
    
    //for (i = 1; i < lenPattern; i++){
    //    if (needle[shift[i - 1]] == needle[i])
    //        shift[i] = shift[i - 1] + 1;
    //    else
    //    {
    //        if (needle[i] == needle[0])//这里有bug，但是leecode通过了，原因是刚好没碰到过不了的测试案例
    //            shift[i] = 1;
    //        else
    //            shift[i] = 0;
    //    }
    //}

    //代码改写如下：
    int j = 0;
    shift[0] = j;
    for (i = 1; i < lenPattern;) {
        if (needle[i] == needle[j])
        {
            j++;
            shift[i] = j;
            i++;      
        }
        else
        {
            if (j == 0)
            {
                shift[i] = 0;
                i++;
            }
            else
            {
                j = shift[j - 1];
            }
                
        }
    }

    j = 0;
    for (i = 0; i < lenHaystack;)
    {
        if (haystack[i] == needle[j])
        {
            i++;
            j++;
            if (j == lenPattern)
                return (i - j);
        }
        else
        {
            if (j == 0)
            {
                i++;
            }
            else
            {                
                j = shift[j - 1];
            }
           
        }       
    }
    return -1;
}

int main()
{
    //char *input = "";
    //char *pattern = "";
    char *input = "BBC ABCDAB ABCDABCDABDE";
    char *pattern = "ABCDABD";
    printf("%d
", strStr(input, pattern));
 
    return 0;
}