＃i nclude <stdio.h>
＃i nclude <stdlib.h>
＃i nclude <string.h>
＃i nclude <time.h>

//获得prefix数组
int* GetPrefixValue(char* strPattern, int iPatternLen)
{
    int i, j; /* i runs through the string, j counts the hits*/
    int* prefix = (int*)malloc(iPatternLen*sizeof(int));
   
    i = 1; j = 0;
    prefix[0] = 0;
   
    while(i<iPatternLen)
    {
        if(strPattern[i] == strPattern[j])
        {
            prefix[i] = ++j;
        }
        else
        {
            j = 0;
            prefix[i] = j;
        }
       
        i++;
    }
   
    return prefix;          
}   

//返回target串在pattern串中第一次匹配的index
int KMPStringMatch(char* strPattern, int iPatternLen, char* strTarget, int iTargetLen, int* prefix)
{
    int i = 0;
    int j = 0;
   
    while(i<iPatternLen && j<iTargetLen)
    {
        if(j==0 || strPattern[i]==strTarget[j])
        {
            i++;  j++;
        }
        else
        {
            j = prefix[j];
        }
    }            
   
    free(prefix);
    
    if(j==iTargetLen)
    {
        return i-j;
    }
    else
    {
        return -1;
    }        
}        

int KMP(char* strPattern, char* strTarget)
{
    int* prefix = GetPrefixValue(strPattern, strlen(strPattern));
    int index = KMPStringMatch(strPattern, strlen(strPattern), strTarget, strlen(strTarget), prefix);
    return index;
}

//在文本文件中查找target串出现的行数
int SearchInTxtFile(char* fileName, char* strTarget)
{
    FILE* hFile = fopen(fileName, "r");
   
    char str[1024];
    int count = 0;
   
   
    while(fgets(str, 1024, hFile)) 
    {
        if(KMP(str, strTarget)!=-1)
        {
            count++;
        }   
    }     
   
    fclose(hFile);
    hFile=NULL;
   
    return count;
}    
            
int main()
{
    char ch;
    char str1[] = "abcabcabctasksb,abTo";
    char str2[] = "abc";
   
    double t=clock();
    printf("%d\n", KMP(str1,str2));
    printf("耗时：%f毫秒！\n", (clock()-t));
   
    t=clock();
    printf("find %d \n", SearchInTxtFile("c:\\txt.txt", "NULL"));
    printf("耗时：%f毫秒！\n", (clock()-t));
    scanf("%c", &ch);

    return 0;
}