实验总结:掌握了字符串的BF匹配算法,在DNA匹配时比较特殊,因为DNA为环状,所以长度要乘以2。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 #define MAX 100 5 int m,n; 6 int BF(char s[],char p[]) 7 { 8 int i=1,j=1,t=1; 9 while(i<=m&&j<=n) 10 { 11 if(s[i]==p[j]) 12 { 13 i++; 14 j++; 15 } 16 else 17 { 18 i=++t;//如果不匹配,主串元素往后移 19 j=1; 20 } 21 } 22 if(j>n)//子串全部匹配成功 23 return 1; 24 else 25 return 0; 26 } 27 int main() 28 { 29 char a[MAX],b[MAX],s[MAX],p[MAX]; 30 while(cin>>b>>a&&a[0]!='0'&&b[0]!='0')//输入不等于0时; 31 { 32 int i,j,flag=0; 33 m=strlen(a); 34 n=strlen(b); 35 for(i=1;i<=m;i++) 36 s[i]=a[i-1]; 37 s[m+1]='\0'; 38 for(i=n;i<2*n;i++)//DNA为环状,所以要两倍 39 b[i]=b[i-n]; 40 b[2*n]='\0'; 41 for(i=0;i<n;i++) 42 { 43 for(j=1;j<=n;j++) 44 p[j]=b[i+j-1]; 45 p[n+1]='\0'; 46 if(BF(s,p)) 47 { 48 flag=1; 49 break; 50 } 51 } 52 if(flag) 53 cout<<"YES"<<endl; 54 else 55 cout<<"NO"<<endl; 56 } 57 return 0; 58 }View Code