数据结构实验报告-串(2)

《数据结构与算法》实验指导V2016 int indexKmp(SqString *s,SqString *t,int start,int next[]); /*串的模式匹配KMP*/

/*生成一个串*/

int strCreate(SqString *s) {

printf(\ gets(s->data);

s->length=strlen(s->data); return OK; }/*strCreate*/

/*（1）---串的模式匹配BF*/

int indexBf(SqString *s,SqString *t,int pos) {

int i=pos-1,j=0;

while(ilength&&jlength) {

if(s->data[i]==t->data[j]) {

i++; j++; } else {

i=i-j+1; j=0; } }

if(j>=t->length) {

return i-t->length+1; } else {

return 0; }

}/*index_bf*/

/*（2）---KMP求next值*/

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

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

while(ilength)

6 《数据结构与算法》实验指导V2016 {

if((j==-1)||(t->data[i]==t->data[j])) {

j++; i++;

next[i]=j; } else {

j=next[j]; } }

}/*getNext*/

/*（3）---KMP模式匹配*/

int indexKmp(SqString *s,SqString *t,int start,int next[]) {

int i=start-1,j=0;

while(ilength&&jlength) {

if(j==-1||s->data[i]==t->data[j]) {

i++; j++; } else {

j=next[j]; } }

if(j>=t->length) {

return i-t->length+1; } else {

return 0; }

}/*index_kmp*/

int main() {

int n,i,pos,next[MAXSIZE]; SqString s,t;

7 《数据结构与算法》实验指导V2016 do {

printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ scanf(\ getchar(); switch(n) {

case 1:

printf(\ printf(\ strCreate(&s); printf(\ strCreate(&t);

printf(\ scanf(\

printf(\ break; case 2:

printf(\ printf(\ strCreate(&s); printf(\ strCreate(&t);

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

for(i=0; i

printf(\ printf(\

printf(\ break; case 0:

exit(0); default: break; } }

8 《数据结构与算法》实验指导V2016 while(n); return 0; }

【实验小结】

9