第1关:基于BF算法的病毒感染监测
来源BJFUOJ
任务描述
医学研究者最近发现了某些新病毒,通过对这些病毒的分析,得知它们的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
//
// Created by feiji on 2022/11/15.
//
#ifndef DATASTRUCTU_H1_H
#define DATASTRUCTU_H1_H
#endif //DATASTRUCTU_H1_H
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define MAXSIZE 2000
//- - - - - 串的堆式顺序存储结构- - - - -
typedef struct
{
char *ch; //若是非空串,则按串长分配存储区,否则ch为NULL
int length; //串的当前长度
}HString;
int Index_BF(HString S,HString T,int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在,则返回值为0
//其中,T非空,1≤pos≤StrLength(S)
int i=pos,j=0;
while(i<=S.length&&j<T.length){
if(S.ch[i]==T.ch[j]){
++i;++j;
}else{i=i-j+1;j=0;}
}
if(j>=T.length) { return 1;}
else{
return 0;
}
}
bool Virus_detection(HString Virus,HString Person)
{//判断是否匹配,如果可以,返回true,否则返回false
//模式匹配算法调用Index_BF函数
HString temp;
int m=Virus.length;
//将病毒长度扩展为2m,复制一份
for(int i=m, j=0;j<m;j++,i++){
Virus.ch[i]=Virus.ch[j];
}
Virus.length=strlen(Virus.ch);
temp.ch = new char[100];
int flag=0;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
temp.ch[j]=Virus.ch[i+j];
}//取出长度为m的所有组合
temp.length=strlen(temp.ch);
flag=Index_BF(Person,temp,0);
if (flag>0||Person.length==1){return true;}
}
return false;
}
BF算法:用于子串的匹配,子串从第一个位置j与模式串i的一个位置依次比较,如果相等++后移,否则i到模式串1的位置,j到子串第一个位置重新匹配。
本题注意:子串为环所以复制一份长度为2m,依次循环取长为m的子串放入temp数组中,执行BF文章来源:https://www.toymoban.com/news/detail-720322.html
BF为暴力求解:时间复杂度 n+m<=T(0)<=n*m文章来源地址https://www.toymoban.com/news/detail-720322.html
到了这里,关于edcoder数据结构第1关:基于BF算法的病毒感染监测的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!