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

刘伟发表于 2006-4-15 16:19

int Index-BF ( SString S, SString T, int pos ) {// 串 S 和 T 均采用定长顺序存储结构，S 和 T 存放串长度。串 S 和 T 均采用定长顺序存储结构，S 和 T 存放串长度。// 返回模式 T 在主串 S 中第 pos 个字符之后的位置，如果不存在，返回模式 T 在主串 S 中第 pos 个字符之后的位置，如果不存在，// 则返回函数值 0。其中 T 非空，1≤pos≤S-T+1-T+1。则返回函数值 0。其中 T 非空，1≤pos≤S-T+1-T+1。i = pos; j = 1;// 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较i = pos; j = 1;// 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较// 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较while ( i <= S && j <= T ) ( i <= S && j <= T ) { if ( S = = T ) { ++i; ++j; ++i; ++j; } // 若字符相等，则继续比较后继字符while ( i <= S && j <= T ) ( i <= S && j <= T ) { if ( S = = T ) { ++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 ) return i–T;else return 0; 0; ( j > T ) return i–T;if ( j > T ) return i–T;else return 0; 0; ( j > T ) return i–T;else return 0; 0;} // Index-BF // Index-BF<div> 　</div><div><pre>//Index_BF.cpp

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#define MAXSTRLEN 255

typedef unsigned char SString; //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&&j<=T)

{ if(S==T)

{++i;

 ++j;

}

 else

{ i=i-j+2;

 j=1;

}

}// end of while

if(j>T) return (i-T);

else return (0);

}//end of Index_BF() function

void main() //main() function

{

SString S,T;

int pos; // 1<=pos<=S-T+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!='\0';m++); // get the length of SString S

S=m-1;

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

T=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

</pre></div>

newbrightness7 发表于 2006-4-20 17:01

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

qswb 发表于 2006-6-18 22:06

有很多种算法呢如bmp、bm

xjtu_yu 发表于 2006-6-20 13:54

好的,谢谢

gssdzc 发表于 2010-6-16 20:18

感谢楼主。。。。。

ywzbismarck 发表于 2011-4-25 13:09

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

发表于 1970-1-1 08:00

页: [1]

数学建模社区-数学中国's Archiver

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