并行计算-实验指导-实验02 串匹配(5)

if(string==NULL) {

printf(\ exit(1); }

for(i=0;i

num=rand()&; string[i]='a'+num;

}

for(j=1;j<(int)(strlen/pedlen);j++)

strncpy(string+j*pedlen,string,pedlen); if((suffixlen=strlen%pedlen)!=0) 2. 源程序 kmp.c #include #include #include #include #include #include

#define MAX(m,n) (m>n?m:n) typedef struct{ int pedlen; int psuffixlen; int pednum; }pntype;

/*对模式串进行周期分析，并计算相应的new和

newval值*/

strncpy(string+j*pedlen,string,suffixle

n);

if((fp=fopen(argv[4],\{

fprintf(fp,\ fclose(fp); } else {

printf(\ exit(1); } return;

}

void Next(char *W,int patlen,int

*nextval,

pntype *pped) {

int i,j,plen;

int *next; if((next=(int

*)malloc((patlen+1)*sizeof(int)))

==NULL) {

printf(\ exit(1); }

/*计算next和nextval*/ next[0]=nextval[0]=-1;

21

j=1;

while(j<=patlen) {

i=next[j-1];

int *prefixlen)

{

matched_num,int *match,int

int i,j;

while(i!=(-1) && W[i]!=W[j-1]) i=matched_num; i=next[i];

next[j]=i+1; if(j!=patlen) {

if( W[j]!=W[i+1]) nextval[j]=i+1; else

nextval[j]=nextval[i+1]; } j++;

}

pped->pedlen=patlen-next[patlen];

pped->pednum=(int)(patlen/pped->pedlen);

pped->psuffixlen=patlen%pped->pedlen; free(next); }

/*改进的KMP算法*/

void kmp(char *T,char*W,int textlen,int

patlen,

int *nextval,pntype

*pped,int

prefix_flag,

j=matched_num; while(i

if((prefix_flag==1)&&((patlen-j)>

(textlen-i))) break;

while(j!=(-1) && W[j]!=T[i])

j=nextval[j]; if(j==(patlen-1))

{

match[i-(patlen-1)]=1;

if(pped->pednum+pped->psuffixlen ==1) j = -1 ;

else

j=patlen-1-pped->pedlen; }

j++;

i++; }

(*prefixlen)=j; }

/*重构模式串以及next函数*/ void

Rebuild_info(int

patlen,pntype

22

*pped,

int *nextval,char *W) {

int i;

if (pped->pednum == 1)

memcpy(W+pped->pedlen,W,

pped->psuffixlen); else

{

memcpy(W+pped->pedlen,W, pped->pedlen);

for (i=3; i<=pped->pednum; i++) {

memcpy(W+(i-1)*pped->pedlen,W, pped->pedlen);

memcpy(nextval+(i-1)*

pped->pedlen, nextval+pped->pedlen, pped->pedlen*sizeof(int)); }

if(pped->psuffixlen!=0) {

memcpy(W+(i-1)*pped->pedlen,W, pped->psuffixlen); memcpy(nextval+(i-1)* pped->pedlen,nextval+ pped->pedlen,

pped->psuffixlen*sizeof(int)); } } }

/*生成文本串*/ void

gen_string(int

strlen,int

pedlen,char *string,

int seed) {

int suffixlen,num,i,j;

srand(seed);

for(i=0;i

num=rand()&; string[i]='a'+num;

}

for(j=1;j<(int)(strlen/pedlen);j++)

strncpy(string+j*pedlen,string,pedlen); if((suffixlen=strlen%pedlen)!=0) strncpy(string+j*pedlen,string,suffixle

n);

}

/*从文件读入模式串信息*/

void GetFile(char *filename,char *place, int *number)

{

FILE *fp;

struct stat statbuf;

if

((fp=fopen(filename,\

{

printf

(\

open

23

file %s\\n\

exit(0);

}

fstat(fileno(fp),&statbuf);

if(((*place)=(char *)malloc(sizeof(char)*

statbuf.st_size)) == NULL){

printf (\

exit(1);

} if

(fread((*place),1,statbuf.st_size,fp)

!=statbuf.st_size){

printf

(\

in

reading

num\\n\

exit(0);

}

fclose (fp);

(*number)=statbuf.st_size;

}

/*打印运行参数信息*/

void PrintFile_info(char *filename,char *T,int id)

{ FILE *fp;

int i;

if ((fp=fopen(filename,\{

printf

(\

open

file %s\\n\

exit(0);

}

fprintf (fp,\Text on node %d is %s .\\n\

id,T);

fclose (fp); }

/*打印匹配结果*/

void PrintFile_res(char *filename,int *t,int len,

int init,int id) { FILE *fp;

int i;

if ((fp=fopen(filename,\

{

printf

(\

open

file %s\\n\

exit(0);

}

fprintf (fp,\the match result on node %d

\\n\

for (i=0; i<=len-1; i++)

if(t[i]==1)

fprintf

(fp,\

+\\n\

else

fprintf

(fp,\

-\\n\

fclose (fp);

24

}

void main(int argc,char *argv[]) { char *T,*W;

int *nextval,*match;

int

textlen,patlen,pedlen,nextlen_send; pntype pped; int

i,myid,numprocs,prefixlen,ready; MPI_Status status;

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

MPI_Comm_rank(MPI_COMM_WORLD, &myid);

nextlen_send=0; ready=1;

/*读如文本串长度*/ textlen=atoi(argv[1]); textlen=textlen/numprocs; pedlen=atoi(argv[2]); if((T=(char

*)malloc(textlen*sizeof(char)))

==NULL) {

printf(\ exit(1); }

gen_string(textlen,pedlen,T,myid);

if(myid==0)

{

PrintFile_info(\ if(numprocs>1)

MPI_Send(&ready,1,MPI_INT,1,0,

MPI_COMM_WORLD);

}

else {

MPI_Recv(&ready,1,MPI_INT,myid-1, myid-1,MPI_COMM_WORLD, &status);

PrintFile_info(\ if(myid!=numprocs-1)

MPI_Send(&ready,1,MPI_INT,

myid+1,myid, MPI_COMM_WORLD); }

printf(\

if((match=(int

*)malloc(textlen*sizeof(int)))

==NULL) { printf(\ exit(1);

}

/*处理器0读入模式串，并记录运行参数

25