数据结构：串：第1关：基于BF算法的病毒感染监测-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构：串：第1关：基于BF算法的病毒感染监测。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

任务描述

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

编程要求

输入

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

输出

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

测试说明

平台会对你编写的代码进行测试：

测试输入： abbab abbabaab baa cacdvcabacsd abc def
0 0

预期输出： YES YES NO

很奇怪，即便是初始状态运行也能打印出一排的YES。大概是因为能打印出YES，意味着result变量中值不为0。而C语言中即便定义没有初始化，里面仍然有值，所以是一排的YES文章来源地址https://www.toymoban.com/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[])
{//字符串旋转,把病毒第一个字符变为最后一个字符
/**************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环状序列是否在患者DNA序列中出现过，出现过返回1，否则返回0
/**************begin************/
int revolTimes=0,flagJudge=0;//flag被BF占了
while(b[revolTimes]!='\0')revolTimes++;//求环形病毒可revolve次数
for(int i=0;i<revolTimes;)//循环控制revolve次数，子串匹配调用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;
}

到了这里，关于数据结构：串：第1关：基于BF算法的病毒感染监测的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！