任務描述

醫(yī)學研究者最近發(fā)現(xiàn)了某些新病毒，通過對這些病毒的分析，得知它們的DNA序列都是環(huán)狀的?，F(xiàn)在研究者收集了大量的病毒DNA和人的DNA數(shù)據(jù)，想快速檢測出這些人是否感染了相應的病毒。為方便研究，研究者將人的DNA和病毒的DNA均表示成由一些小寫字母組成的字符串，然后檢測某種病毒的DNA序列是否在患者的DNA序列中出現(xiàn)過，如果出現(xiàn)過，則此人感染了病毒，否則沒有感染。注意：人的DNA序列是線性的，而病毒的DNA序列是環(huán)狀的。請使用BF算法檢測人是否感染相應病毒。

編程要求

輸入

多組數(shù)據(jù)，每組數(shù)據(jù)有一行，為序列A和B，A對應病毒的DNA序列，B對應人的DNA序列。A和B都為“0”時輸入結束。

輸出

對于每組數(shù)據(jù)輸出一行，若患者感染了病毒輸出“YES”，否則輸出“NO”。

測試說明

平臺會對你編寫的代碼進行測試：

測試輸入： abbab abbabaab baa cacdvcabacsd abc def
0 0

預期輸出： YES YES NO

很奇怪，即便是初始狀態(tài)運行也能打印出一排的YES。大概是因為能打印出YES，意味著result變量中值不為0。而C語言中即便定義沒有初始化，里面仍然有值，所以是一排的YES文章來源地址http://www.zghlxwxcb.cn/news/detail-743951.html

#include<iostream>
#include<cstring>
#define MAXSIZE 1000
using namespace std;
int BF(char a[],char b[])
{//簡單模式匹配算法,匹配成功返回1，否則返回0
/**************begin************/
 int i=0,flag=0,tem;
for(;a[i]!='\0';i++)//每次失敗，主串右移一位
 {
     int tem=i,j=0;//每次比較不匹配后i才能++,但每比完一個字符若正確要比較下一個
     for(;b[j]!='\0';j++,tem++)//和主串比較
     {
         if(a[tem]!=b[j]) 
         {
             break;
         }
     }
     if(b[j]=='\0') 
     {
        flag=1;//在如果不匹配，主串就右移，子串就從頭比較的情況下，只有子串全部匹配，子串才能遍歷到最后的'\0'
        break;
     }
 }
 return flag;



    /**************end************/
}
void Revolve(char a[])
{//字符串旋轉,把病毒第一個字符變?yōu)樽詈笠粋€字符
/**************begin************/
 char tem=a[0];
 int i=1;
 for(;a[i]!='\0';i++)
 {
     a[i-1]=a[i];
 }
 a[i-1]=tem;



    /**************end************/
}
int Judge(char b[],char a[])//和BF的形參有些許不同
{//判別病毒DNA環(huán)狀序列是否在患者DNA序列中出現(xiàn)過，出現(xiàn)過返回1，否則返回0
/**************begin************/
int revolTimes=0,flagJudge=0;//flag被BF占了
while(b[revolTimes]!='\0')revolTimes++;//求環(huán)形病毒可revolve次數(shù)
for(int i=0;i<revolTimes;)//循環(huán)控制revolve次數(shù)，子串匹配調用BF()方法
{
    int flag=BF(a,b);
    if(flag==0)//如果不匹配,revolve后再比較
    {
        Revolve(b);
        i++;
    }
    else 
    {
        flagJudge=1;
        break;
    }
}
return flagJudge;
 

  
    /**************end************/
}
int main()
{
	char a[MAXSIZE],b[MAXSIZE];//a存入病毒的DNA序列，b存入人的DNA序列
	while(cin>>a>>b)
	{
	    if(strcmp(a,"0")==0&&strcmp(b,"0")==0)
            break;
        int result=Judge(a,b);//即便Judge沒有返回1或0，result仍有未知的殘留值，所以初始代碼也能打印出YES
        if(result)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
 	}
	return 0;
}

到了這里，關于數(shù)據(jù)結構：串：第1關：基于BF算法的病毒感染監(jiān)測的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！