我要小红花:PP
int 0x080
#include <assert.h>
#include <errno.h>
#include <string.h>
static int *
get_next( const char *const str )
{
int *next,len=strlen(str),i,j;
assert(NULL!=(next=(int *)malloc(sizeof(int)*(len))));
for(next[0]=-1,i=1,j=-1; i<len; ++i ){
for(j=i-1;j!=-1&&str[j]!=str[next[j]];j=next[j])
;
next[i]=(j!=-1&&str[j]==str[next[j]])?next[j]+1:0;
}
return next;
}
static int *
get_nextval( const char *const str )
{
int i,j,len=strlen(str),*next=get_next( str );
for(i=1; i<len; ++i){
if((j=next[i])!=0&&str[i]==str[j])
next[i]=next[j];
}
return next;
}
#define MAX 256
int
main(int argc, char **argv)
{
FILE * input=NULL;
char buf[MAX],patt[MAX];
if(argc != 2){
fprintf(stderr,"Usage:./a.out <Input_file_name>");
exit(1);
}
if( NULL == (input=(fopen(argv[1],"r"))) ){
fprintf(stderr,"%s==>%s",argv[1],strerror(errno));
exit(1);
}
fprintf(stdout,"patt:");
scanf("%s",patt);
int count=0;/*这个是来统计的变量*/
int * next=get_nextval(patt);
while(NULL != fgets(buf,MAX,input)){
int i=0,j=0;
while(i<=strlen(buf)){
if(j==strlen(patt))j=0,++count;
j=(-1==j)?(++i,0):buf[i]==patt[j]?(++i,j+1):next[j];
}
}
fprintf(stdout,"%d",count);
fclose(input);
exit(0);
}
汪军
来来去去
int 0x080
汪军 写道：
> 注释好少啊...
汪军
就是KMP匹配算法,nextval的求值书上讲的更详细的:)
汪军 写道：
> 注释好少啊...
汪军的签名
colitas
rain.man
--
▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁
╲█◤
◢█◥◣ Good Good Life , Day Day Study ! ◣◢
◤◥ -- rainman ◥◣█◤
_____________________________________________◢█╲ _____
汪军
网址在上面,你也可以用google搜索c++编程规范,希望愿意加入程序员行列的朋友都读一读,很有用处
colitas
Yiqiang Luo
http://groups.google.com/group/hydil/browse_thread/thread/ae6d6217e158fbff/18ab7743126edaee?lnk=gst&q=%E7%BC%96%E7%A8%8B%E8%A7%84%E8%8C%83&rnum=1#18ab7743126edaee
网址在上面,你也可以用google搜索c++编程规范,希望愿意加入程序员行列的朋友都读一读,很有用处
xue hang
Yiqiang Luo
多谢了！！！