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

《KMP字符串匹配算法C语言实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KMP字符串匹配算法C语言实现(转)记录下来先＃include＃include＃include＃include//获得prefix数组int*GetPrefixValue(char*strPattern,intiPatternLen){   inti,j;/*irunsthroughthestring,jcountsthehits*/   int*prefix=(int*)malloc(iPatternLen*sizeof(int));      i=1;j=0;   prefix

2、[0]=0;      while(i

3、Match(char*strPattern,intiPatternLen,char*strTarget,intiTargetLen,int*prefix){   inti=0;   intj=0;      while(i

4、

5、strPattern[i]==strTarget[j])       {           i++; j++;       }       else       {           j=prefix[j];       }   }    

6、              free(prefix);       if(j==iTargetLen)   {       returni-j;   }   else   {       return-1;   }        }        intKMP(char*strPattern,char*strTarget){   int*prefix=GetPrefixValue(strPattern,strlen(strPattern));   intindex=KMPStringMatch(strPattern,strlen(strPattern),

7、strTarget,strlen(strTarget),prefix);   returnindex;}//在文本文件中查找target串出现的行数intSearchInTxtFile(char*fileName,char*strTarget){   FILE*hFile=fopen(fileName,"r");      charstr[1024];   intcount=0;         while(fgets(str,1024,hFile))    {       if(KMP(str,strTarget)!=-1)       {      

8、     count++;       }      }           fclose(hFile);   hFile=NULL;      returncount;}                intmain(){   charch;   charstr1[]="abcabcabctasksb,abTo";   charstr2[]="abc";      doublet=clock();   printf("%d",KMP(str1,str2));   printf("耗时：%f毫秒！",(clock()-t));      t=cl

9、ock();   printf("find%d",SearchInTxtFile("c:\txt.txt","NULL"));   printf("耗时：%f毫秒！",(clock()-t));   scanf("%c",&ch);   return0;}