＃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;
}?