病毒感染监测 - 海月CSDN

描述

医学研究者最近发现了某些新病毒，通过对这些病毒的分析，得知它们的DNA序列都是环状的。现在研究者收集了大量的病毒DNA和人的DNA数据，想快速检测出这些人是否感染了相应的病毒。为方便研究，研究者将人的DNA和病毒的DNA均表示成由一些小写字母组成的字符串，然后检测某种病毒的DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了病毒，否则没有感染。注意：人的DNA序列是线性的，而病毒的DNA序列是环状的。

输入

多组数据，每组数据有一行，为序列A和B，A对应病毒的DNA序列，B对应人的DNA序列。A和B都为“0”时输入结束。

输出

对于每组数据输出一行，若患者感染了病毒输出“YES”，否则输出“NO”。

输入样例 1 

abbab abbabaab
baa cacdvcabacsd
abc def   
0 0

输出样例 1

YES
YES
NO

#include<iostream>
#include<string>
using namespace std;

int Index_BF(const string &str1, const string &str2, int pos)
{

    int i = pos;
    int j = 0;
    int len1 = str1.size();
    int len2 = str2.size();
    while (i<len1&&j<len2)
    {
    	//cout<<"Now compare:"<<str1[i]<<":"<<str2[j]<<endl;
        if (str1[i] == str2[j])
        {
            i++;
            j++;
            //cout<<"P："<<str1[i]<<"=="<<str2[j]<<"("<<i<<","<<j<<")"<<endl;; 
        }
        else
        {
        	//cout<<"B："<<str1[i]<<"!="<<str2[j]<<"("<<i<<","<<j<<")"<<endl;; 
            i = i - j + 1;
            j = 0;
            
           // cout<<"["<<i<<"->"<<i - j + 1<<"],j=0"<<endl;
        }
    }
    if (j >= len2)
        return i - len2;
    else
        return -1;
}

int main()
{
    int pos = 0;
    string str1;
    string str2;
    string temp;
    int flag,m,i,j;
    while (cin >> str2 >> str1)
    {
        if (str1 == "0"&&str2 == "0")break;
		string str3=str2+str2;
        m=str2.length();	
		//cout<<str3<<endl;		
      	for(i=0;i<m;i++)
      	{
         	temp=str3.substr(i,m);	
		///	cout<<temp<<endl;	
         	flag=Index_BF(str1,temp,0);	
        	if(flag!=-1) break;			
      	}//for
     	if(flag!=-1)
         cout<<"YES"<<endl;
      	else
         cout<<"NO"<<endl;      
    }
    return 0;
}