随笔 - 7  文章 - 15  trackbacks - 0
<2011年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(2)

随笔档案(7)

相册

搜索

  •  

积分与排名

  • 积分 - 14210
  • 排名 - 895

最新评论

阅读排行榜

评论排行榜

#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;

posted on 2006-07-05 23:48 Bourne 阅读(4346) 评论(4)  编辑 收藏 引用

FeedBack:
# re: KMP字符串匹配算法C语言实现 2009-02-18 13:24 杨如清
错误的算法
char str1[] = "abcabcabctasksb,abTo";
char str2[] = "sb";
KMP(str1,str2)返回0  回复  更多评论
  
# re: KMP字符串匹配算法C语言实现 2009-02-27 19:46 gaewah
的确好像错了厄。。
abaababaab
的prefix算错了。。  回复  更多评论
  
# re: KMP字符串匹配算法C语言实现 2009-08-17 14:45 test
简直就一垃圾 这样的代码也贴出来!  回复  更多评论
  
# re: KMP字符串匹配算法C语言实现 2011-06-17 10:04 学校
楼上有点偏激了。。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理