edcoder数据结构第1关:基于BF算法的病毒感染监测

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

第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

BF为暴力求解:时间复杂度 n+m<=T(0)<=n*m文章来源地址https://www.toymoban.com/news/detail-720322.html

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构》实验报告四:串的模式匹配(BF算法、KMP算法)

    1、了解 串 的基本概念。 2、掌握 串的模式匹配算法 的实现 。 说明以下概念 1、模式匹配:          串的模式匹配就是 子串的定位运算 。          设有两个字符串 S 和 T ,S为 主串(正文串) ,T为 子串(模式串) 。在主串S中查找与模式串T相匹配的子串,若匹配成功,确定

    2024年02月01日
    浏览(55)
  • 【数据结构】字符串匹配|BF算法|KMP算法|next数组的优化

    字符串匹配算法是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目,本文主要介绍BF算法(最好想到的算法,也最好实现)和KMP算法(最经典的) BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式串T的第一

    2024年02月04日
    浏览(53)
  • 算法复现 - 病毒感染检测(案例4.1算法4.5)

    第1关:案例4_1 病毒感染检测

    2024年02月06日
    浏览(35)
  • 勒索病毒最新变种.halo勒索病毒来袭,如何恢复受感染的数据?

    摘要: .halo勒索病毒已成为数字世界中的威胁,通过高级加密技术将文件锁定,并要求支付赎金。本文91数据恢复将深入介绍.halo勒索病毒的工作原理,提供解锁被感染文件的方法,以及探讨如何有效预防这一威胁。如果您正在经历勒索病毒数据恢复的困境,我们愿意与您分享

    2024年02月09日
    浏览(39)
  • 勒索病毒最新变种.faust勒索病毒来袭,如何恢复受感染的数据?

    引言: 随着我们进入数字化时代,数据的重要性变得愈发显著,而网络安全威胁也日益增加。.faust勒索病毒是其中一种备受恶意分子钟爱的危险工具,它通过加密用户文件并勒索高额赎金来对个人和组织发起攻击。本文将深入探讨.faust勒索病毒的威胁,包括其工作原理、如何

    2024年02月21日
    浏览(44)
  • Mallox勒索病毒最新变种.malox勒索病毒来袭,如何恢复受感染的数据?

    Mallox勒索病毒是一种针对计算机系统的恶意软件,能够加密受感染计算机上的文件。最近,新的Mallox病毒变种.malox勒索病毒被发现并引起了关注,.malox勒索病毒这个后缀已经是Mallox勒索病毒家族的第十几个升级变种了,这个后缀的加密占比更高,导致数据的修复难度再次升级

    2024年02月06日
    浏览(41)
  • 服务器感染了.360勒索病毒,如何确保数据文件完整恢复?

    引言: 随着科技的不断进步,互联网的普及以及数字化生活的发展,网络安全问题也逐渐成为一个全球性的难题。其中,勒索病毒作为一种危害性极高的恶意软件,在近年来频频袭扰用户。本文91数据恢复将重点介绍 360 勒索病毒,包括如何解密被其加密的数据文件,以及如

    2024年02月12日
    浏览(46)
  • 服务器感染了.mallox勒索病毒,如何确保数据文件完整恢复?

    尊敬的读者: 随着科技的进步,网络犯罪也在不断演进,.mallox勒索病毒作为其中的一种威胁已经引起了广泛关注。本文将深入介绍.mallox勒索病毒的特征、传播途径,详细解释如何有效恢复被加密的数据文件,并提供一系列预防措施,以保护系统免受.mallox及类似威胁的侵害。

    2024年02月20日
    浏览(35)
  • 服务器感染了.Elbie勒索病毒,如何确保数据文件完整恢复?

    引言: 在数字时代,数据是我们生活和工作的重要组成部分。然而,恶意软件的威胁日益增加,其中 Elbie 勒索病毒以其毒辣的加密手段和无情的勒索要求,让人防不胜防。本文91数据恢复将为你剖析 Elbie 勒索病毒的独特之处,并探讨解密被其束缚的数据文件的方法,更重要

    2024年02月11日
    浏览(41)
  • 服务器感染了.pings勒索病毒,如何确保数据文件完整恢复?

    导言: 随着科技的不断进步,网络犯罪也在不断演变。其中之一的.pings勒索病毒是一种危险的恶意软件,它能够加密用户的数据文件,并要求支付赎金以解密这些文件。在本文中,91数据恢复将介绍.pings勒索病毒,以及如何恢复被其加密的数据文件,并提供一些预防措施。

    2024年01月25日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包