数据结构串匹配源代码 已经运行成功的

#include #include #define MAXSIZE 100 typedef struct{ char data[MAXSIZE];

int length; }SqString;

int index_bf(SqString *s,SqString *t,int start); void getNext(SqString *t,int next[]);

int index_kmp(SqString *s,SqString *t,int start,int next[]); void show_index();

int index_bf(SqString *s,SqString *t,int start){ int i=start; int j=1; while(i<=s->length &&j<=t->length ){

if(s->data[i]==t->data[j]) {++i;++j;} else{i=i-j+2; j=1;} }

if(j>t->data[0]) return i-t->data[0]; else return 0;

}

void getNext(SqString *t,int next[]){

int i=0,j=-1; next[0]=-1;

while(ilength){ if((j==-1)||(t->data[i]==t->data[j])){ i++;j++;next[i]=j;

}else j=next[j];

}

}

int index_kmp(SqString *s,SqString *t,int start,int next[]){ int i=start;int j=1;

while(i<=s->length &&j<=t->length ){ if(j==0||s->data[i]==t->data[j]) {++i; ++j;} }

if(j>t->data[0]) return i-t->data[0]; else return 0;

else j=next[j];

}

void show_index(){ SqString s,t;

int k,next[MAXSIZE]={0},i; printf(\ printf(\ gets(s.data);

s.length=strlen(s.data); printf(\ gets(t.data);

t.length=strlen(t.data); printf(\ scanf(\

printf(\ getNext(&t,next); printf(\ printf(\

for(i=0;i

printf(\ printf(\}

int main(){ show_index(); return 0; }