KMP算法的实现：

#include
#include
#include

int strStr(char* haystack, char* needle) {
if (haystack == NULL || needle == NULL)
return -1;
if (needle[0] == '\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\n", strStr(input, pattern));

return 0;  

}