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

int *GetNext(char *match)
{
    int i;
    i = 1;
    int *pNext = NULL;
    pNext = (int*)malloc(sizeof(int)*strlen(match));
    pNext[0] = 0;

    int j;
    j = i-1;
    while(i < strlen(match))
    {
        if(match[i] == match[pNext[j]])
        {
            pNext[i] = pNext[j]+1;
            i++;
            j = i-1;
        }
        else if(pNext[j] == 0)
        {
            pNext[i] = 0;
            i++;
            j = i-1;
        }
        else
        {
            j = pNext[j]-1;
        }
    }

    return pNext;
}

int KMP(char *src,char *match)
{
    if(src == NULL || match == NULL)return -1;

    int *pNext = NULL;

    //获得Next数组
    pNext = GetNext(match);

    //查找
    int i;
    int j;
    i = 0;
    j = 0;
    while(i < strlen(src)&& j<strlen(match))
    {
        if(src[i] == match[j])
        {
            i++;
            j++;
        }
        else
        {
            //不想等 且匹配串已经回到开始位置仍不相等 主串向后移动
            if(j == 0)
            {
                i++;
            }

            //匹配串向前移动
            else
            {
                j = pNext[j-1];
            }
        }
    }

    //匹配串已经走完  结束
    if(j == strlen(match))
    {
        return i-j;
    }
    return -1;
}

int main()
{
    char *src = "ahfhawoerqhewqlknxcabcabcdabcabcfjfesaruwqou";
    char *match = "abcahseifysfryewbcdabcabcf";
    int n;
    n = KMP(src,match);
    printf("%d\n",n);
    return 0;
}