[原创]发一道数据结构上机题（串的匹配）

刘伟

 

int Index-BF ( SString S, SString T, int pos ) {

// 串 S 和 T 均采用定长顺序存储结构，S[0] [0] 和 T[0] 存放串长度。

串 S 和 T 均采用定长顺序存储结构，S[0] [0] 和 T[0] 存放串长度。

// 返回模式 T 在主串 S 中第 pos 个字符之后的位置，如果不存在，

返回模式 T 在主串 S 中第 pos 个字符之后的位置，如果不存在，

// 则返回函数值 0。其中 T 非空，1≤pos≤S[0]-T[0]+1[0]-T[0]+1。

则返回函数值 0。其中 T 非空，1≤pos≤S[0]-T[0]+1[0]-T[0]+1。

i = pos; j = 1;

// 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较

i = pos; j = 1;

// 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较

// 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较

while ( i <= S[0] && j <= T[0] ) ( i <= S[0] && j <= T[0] ) {

if ( S = = T[j] ) { ++i; ++j; ++i; ++j; } // 若字符相等，则继续比较后继字符

while ( i <= S[0] && j <= T[0] ) ( i <= S[0] && j <= T[0] ) {

if ( S = = T[j] ) { ++i; ++j; ++i; ++j; } // 若字符相等，则继续比较后继字符

{ ++i; ++j; ++i; ++j; } // 若字符相等，则继续比较后继字符

else { i = i – j + 2; j = 1; i = i – j + 2; j = 1; } // 若字符不等，则指针后退重新开始匹配

{ i = i – j + 2; j = 1; i = i – j + 2; j = 1; } // 若字符不等，则指针后退重新开始匹配

} // while 结束

} // while 结束

if ( j > T[0] ) return i–T[0];

else return 0; 0;

( j > T[0] ) return i–T[0];

if ( j > T[0] ) return i–T[0];

else return 0; 0;

( j > T[0] ) return i–T[0];

else return 0; 0;

} // Index-BF

// Index-BF

　

//Index_BF.cpp



#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#define MAXSTRLEN 255



typedef unsigned char SString[MAXSTRLEN+1];                    //from 0 to 256 becoz of '\0'



int Index_BF(SString S,SString T,int pos)                      //Index_BF() function

{

    int i=pos,j=1;                                             //from the pos char in main SString on

	while(i<=S[0]&&j<=T[0])

	{ if(S==T[j])

		{++i;

	     ++j;

		}

	   else

		{ i=i-j+2;

	      j=1;

		}

	}// end of while

	if(j>T[0]) return (i-T[0]);

    else return (0);

}//end of Index_BF() function



 

void main()                                                     //main() function

{

   SString S,T;

   int pos;                                                     //  1<=pos<=S[0]-T[0]+1;

   int m,n,r;                                                   //  the length of SString S and T

   cout<<"Index_BF.cpp"<<endl<<"============"<<endl<<endl;

   cout<<"Please input the Main SString S: <eg. student> ";

   cin.getline(S+1,MAXSTRLEN);

   cout<<"Please input the SString T : <eg. den> ";

   cin.getline(T+1,MAXSTRLEN);

   cout<<"From ? on: <eg. 1> ";

   cin>>pos;



   for(m=0;S[m]!='\0';m++);                                      // get the length of SString S

   S[0]=m-1;

   for(n=0;T[n]!='\0';n++);                                      // get the length of SString T 

   T[0]=n-1;

 

   if(r=Index_BF(S,T,pos))                                

	  cout<<endl<<"The postion of T in the Main SString S is: "<<r<<endl<<"...OK...!"<<endl;

   else cout<<"Failure to Index the SString!"<<endl;

   getch();

}//end of main() function

newbrightness7

好，学习一下，谢谢楼主！

qswb

有很多种算法呢

如bmp、bm

xjtu_yu

好的,谢谢

gssdzc

感谢楼主。。。。。

ywzbismarck

好，学习一下，谢谢楼主！