C语言KMP字符串搜索算法实现。_c语言吧

60.208.83.*

1楼

// MyKMP.cpp : Defines the entry point for the console application.
#include "stdafx.h"

int next[255];
char pat[]="aacaab";
char str[]="fsoifhewgsdksdkfhsdifhewhfefksdhfdsoihfoehfosdhfdsaacaab";

void getNext(char pat[], int next[])
{

int j=0;
for(int i=0;pat[i];i++)
{
if(i==0) next[i]=-1;
else
{
if(pat[i]==pat[j])
{
++i;
++j;
next[i]=j;
}
else j=next[j];
}

}
}

int KMP(char *str1, char*pat, int *next)
{
int i=0,j=0;
while(str[i])
{
if(pat[j]==0) return i-j;
if(j==0 || str[i]==pat[j]){
++i;
++j;
}
else j=next[j];
}
if(pat[j]==0) return i-j;
return -1;
}

int main(int argc, char* argv[])
{
int i;
getNext(pat,next);
int result=KMP(str,pat,next);
printf("%s\n",str);
for(i=0;i<result;i++) printf(" ");
printf("%s\n",pat);
printf("at %d\n",result);
return 0;
}

2005-3-26 10:40
回复

sunnisdu 2位粉丝	2楼不错
2005-3-26 10:41 回复

sunnisdu
2位粉丝

3楼

int next[255];
char pat[]="aacaab";
char str[]="fsoifhewgsdksdkfhsdifhewhfefksdhfdsoihfoehfosdhfdsaacaab";

void getNext(char pat[], int next[])
{
int i;
int j=0;
for(i=0;pat[i];i++)
{
if(i==0) next[i]=-1;
else
{
if(pat[i]==pat[j])
{
++i;
++j;
next[i]=j;
}
else j=next[j];
}

}
}

int KMP(char *str, char*pat, int *next)
{
int i=0,j=0;
while(str[i])
{
if(pat[j]==0) return i-j;
if(j==0 || str[i]==pat[j]){
++i;
++j;
}
else j=next[j];
}
if(pat[j]==0) return i-j;
return -1;
}

int main(int argc, char* argv[])
{
int i;
int result;
getNext(pat,next);
result=KMP(str,pat,next);
printf("%s\n",str);
for(i=0;i<result;i++) printf(" ");
printf("%s\n",pat);
printf("at %d\n",result);
return 0;
}

2005-3-26 11:18
回复

vc99 34位粉丝	4楼又来个高手?呵呵，希望坚持来...
2005-3-27 00:38 回复

59.66.75.*	5楼明显有错误
2005-9-19 13:59 回复

fisherman1981
0位粉丝

6楼

有错误！！！
以下是我写的，getNext正确,但是，index_KMP还是有问题，哪位高手帮我改改！
/*KMP算法*/

/*a string begins with index of 0 and ends with the char '\0'*/
void getNext(char pat[], int next[])
{
int j = 0;
int k = -1;
next[0] = -1;

while (pat[j])
{
if ( k == -1 || pat[j] == pat[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}

int index_KMP(char str[], char pat[])
{
int i = 0;
int j = 0;
int next[255];

getNext(pat, next);

while (str[i])
{
if (pat[j] == '\0')
{
return (i - j);
}
if (j == -1 || str[i] == pat[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
return -1;
}

2005-11-26 13:45
回复

fisherman1981 0位粉丝	7楼思路见严蔚敏的书！
2005-11-26 13:48 回复

211.87.199.*	8楼有没有关于KMP的论文啊
2006-4-29 14:42 回复

218.94.9.*

9楼

#include <stdio.h>
void getNext(char pat[], int next[])
{
int j = 0;
int k = -1;
next[0] = -1;

while (pat[j])
{
if ( k == -1 || pat[j] == pat[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}

int index_KMP(char str[], char pat[])
{
int i = 0;
int j = 0;
int next[255];

getNext(pat, next);

while (str[i])
{
if (pat[j] == '\0')
{
return (i - j);
}
if (str[i] == pat[j])
{
i++;
j++;
continue;
}

i += next[j+1]+1;

}
if (pat[j] == '\0')
{
return (i - j);
}
return -1;
}
//在原书中数组是从1开始的，所以导致直接抄写不可能的到正确结果

2006-5-25 16:49
回复

59.41.252.*	10楼请有留下程序的同志们留下你们的QQ吧~~~~~~~~~
2006-5-29 19:13 回复

218.25.56.*	11楼 c gjctgzj
2006-6-13 20:49 回复

59.34.3.*

12楼

我觉得这个比上面的要好，上面的不考虑pattern的大小，只定义一个next【255】很耗内存的。下面这个可以显示运行时间而且根据具体的pattern来计算next
＃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 == strPattern[j])
{
prefix = ++j;
}
else
{
j = 0;
prefix = 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==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;
}

2006-11-30 11:09
回复

60.213.186.*	13楼楼主系垃圾啊数组下标都不对
2007-1-11 09:52 回复

59.52.5.*	14楼加注释好不最好将算法讲清楚不然看的很累
2007-3-24 13:17 回复

59.52.5.*	15楼加注释好不最好将算法讲清楚不然看的很累
2007-3-24 14:03 回复

220.201.38.*	16楼什么叫KMP字符串？
2007-5-9 09:56 回复

211.99.23.*	17楼技术论坛、技术博客即将开张，嘿嘿，欢迎热爱论坛，热爱IT，喜爱用博客写下IT人生的，对网络世界有一定了解的兄弟姐妹加入，有意者请加QQ：460456806
2007-5-9 09:58 回复

222.244.236.*

18楼

void get_nextval(const char *T, int next[])

{

// 求模式串T的next函数值并存入数组 next。

int j = 0, k = -1;

next[0] = -1;

while ( T[j/*+1*/] != '\0' )

{

if (k == -1 || T[j] == T[k])

{

++j; ++k;

if (T[j]!=T[k])

next[j] = k;

else

next[j] = next[k];

}// if

else

k = next[k];

}// while

////这里是我加的显示部分

// for(int i=0;i<j;i++)

//{

// cout<<next[i];

//}

//cout<<endl;

}// get_nextval　

另一种写法，也差不多。

void getNext(const char* pattern,int next[])

{

next[0]= -1;

int k=-1,j=0;

while(pattern[j] != '\0')

{

if(k!= -1 && pattern[k]!= pattern[j] )

k=next[k];

++j;++k;

if(pattern[k]== pattern[j])

next[j]=next[k];

else

next[j]=k;

}

////这里是我加的显示部分

// for(int i=0;i<j;i++)

//{

// cout<<next[i];

//}

//cout<<endl;

}

下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数

#include <iostream.h>

#include <string.h>

int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。

{

if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//

return -1;//空指针或空串，返回-1。

int len=0;

const char * c=Pattern;

while(*c++!='\0')//移动指针比移动下标快。

{

++len;//字符串长度。

}

int *next=new int[len+1];

get_nextval(Pattern,next);//求Pattern的next函数值

int index=0,i=0,j=0;

while(Text[i]!='\0' && Pattern[j]!='\0' )

{

if(Text[i]== Pattern[j])

{

++i;// 继续比较后继字符

++j;

}

else

{

index += j-next[j];

if(next[j]!=-1)

j=next[j];// 模式串向右移动

else

{

j=0;

++i;

}

}

}//while

delete []next;

if(Pattern[j]=='\0')

return index;// 匹配成功

else

return -1;

}

int main()//abCabCad

{

char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";

char*pattern="adCadCad";

//getNext(pattern,n);

//get_nextval(pattern,n);

cout<<KMP(text,pattern)<<endl;

return 0;

}

2007-5-29 10:18
回复

倜傥霸主 0位粉丝	19楼我不会啊怎么我学C语言这么笨啊是不是我不适合变程序啊那为高人帮帮我啊我很想学好C语言啊
2007-6-13 12:03 回复

202.108.77.*	20楼有错误阿大哥你真的台Nb了！
2007-7-5 09:07 回复

219.133.40.*	21楼垃圾
2007-9-30 15:07 回复

MasterRaySoul 4位粉丝	22楼 void GetNext(char pat, int next) { int i=0, j=-1; next[0]=-1; while (pat[i]) { if (j==-1 \|\| pat[i]==pat[j]) next[++i]=++j; else j=next[j]; } } int KMP(char str, char pat) { int i=0, j=0; while (str[i]) { if (pat[j]=='\0') return i-j; if (j==0 \|\| str[i]==pat[j]) { i++; j++; } else j=next[j]; } if (pat[j]=='\0') return i-j; return -1; }
2007-9-30 17:59 回复

58.17.23.*	23楼这不光是学了Ｃ语言就能编的呀，所以某些同学不要气馁，这是数据结构里面的知识，ＫＭＰ的确要花时间好好看看，今天上课才学的，还没怎么弄懂，呵呵，谢谢高手们的程序呀！
2007-10-10 22:14 回复

zhangbaokun0 0位粉丝	24楼程序写出来没啥，有算法照着抄有基础的都能写出来，能明白其中的原理或者是设计出类似的算法就是高手了
2007-10-10 22:17 回复

61.167.119.*	25楼谢谢大家哦
2007-10-25 08:24 回复

myshinji 1位粉丝	26楼说真的,很不愿意到baidu来找代码……
2007-10-25 11:56 回复

MasterRay 22位粉丝	27楼百度“吃”空格（还要用、 代替）、TAB
2007-10-25 20:27 回复

115.48.106.*	28楼　%#sed　%#qi 请问哪个高手帮下忙，转义下，谢谢
2008-10-4 07:28 回复

119.120.49.*

29楼

为什么大家写的算法，跟我在书上看的理解都不同呢？
因为结果不同，
像字符串"ababcabababc"我在书上看的结果应该是011231234545
但大家的算法都得到 0 0 1 2 0 1 2 3 4 3 4 5
怎么会这样？
我的算法写得不好，是这样的。
void get_next(char* chars) //生成next值的函数
{
int i,j,temp;

i = 1;
j = 0;
next[1] = 0;

while(i<13)
{
if(j==0 && i==1) //第二位的next应该都为1
{
++i;++j;
next[i] = j;
}
else if(chars[i-1]!=chars[next[i]-1])//当测试next值上的数据与当前数据不等时进行
{
j = next[i]; //取得next值

while(chars[j-1]!=chars[i-1]) //如当前的值，与下一next值也不同，j值继续后退
{
temp = j; //取得前一next值
j = next[j]; //前一next值
if(j<=0)
{
next[i+1] = 1;
++i;
break;
}
else if(chars[j-1]==chars[i-1])
{
next[i+1] = next[temp] + 1;
++i;
break;
}
}

}
else if(chars[i-1]==chars[next[i]-1]) //当测试next值上的数据与当前数据相等时进行
{
next[i+1] = next[i] + 1;
++i;
}
}
}

2009-1-3 13:23
回复



内　容:
用户名:
验证码:	请点击后输入验证码，加入会员后本吧发贴免验证码。

C语言KMP字符串搜索算法实现。

发表回复