KMP字符串匹配算法C语言实现.doc

KMP字符串匹配算法C语言实现 (转)记录下来先i nclude i nclude i nclude i nclude /获得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; prefix0 = 0; while(iiPatternLen) if(strPatterni = strPatternj) prefixi = +j; else j = 0; prefixi = 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(iiPatternLen & jiTargetLen) if(j=0 | strPatterni=strTargetj) i+; j+; else j = prefixj; 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 str1024; 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(%dn, KMP(str1,str2); printf(耗时：%f毫秒！n, (clock()-t); t=clock(); printf(find %d n, SearchInTxtFile(c:tx