利用BF算法进行病毒检测的方法探析
最编程
2024-07-23 15:31:08
...
人的DNA和病毒DNA均表示成由一些字母组成的字符串序列。然后检测某种病毒DNA序列是否在患者的DNA序列中出现过,如果出现过,则此人感染了该病毒,否则没有感染。例如,假设病毒的DNA序列为baa,患者1的DNA序列为aaabbba,则感染,患者2的DNA序列为babbba,则未感染。(注意,人的DNA序列是线性的,而病毒的DNA序列是环状的)
输入格式:
输入第一行中给出1个整数i(1≤i≤11),表示待检测的病毒DNA和患者DNA的对数。
输入i行串序列,每行由两个字符串组成(字符串中不含不可见字符),两字符串之间用一个空格分隔,分别代表病毒的DNA序列和患者的DNA序列,病毒的DNA序列和患者的DNA序列长度不超过500。
输出格式:
依次逐行输出每对检测样本的结果,感染输出:YES,未感染输出:NO。
输入样例1:
1
baa bbaabbba
输出样例1:
YES
输入样例2:
2
cced cdccdcce
bcd aabccdxdxbxa
输出样例2:
YES
NO
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int BF(char S[], char T[], char A[])//BF算法
{
int i = 0, j = 0;//i标记母串S,j标记子串T
while (i < strlen(S) && j < strlen(A))
{
if (S[i] == T[j])//相等,都往下
{
i++;
j++;
}
else//不等,母串回溯
{
i = i - j + 1;
j = 0;
}
}
if (j >= strlen(A)) return 1;
else return 0;
}
int main()
{
char a[501], b[501];
int n, flag = 0;
cin >> n;//待测对数
for (int i = 0; i < n; i++)
{
cin >> a;//输入病毒串
getchar();
cin >> b;//输入DNA
char c[1000];
for (int i = 0; i < strlen(a); i++)//病毒串为环串,遍历每种可能
{
int k = i;
for (int j = 0; j < strlen(a); j++)//c赋值为该次判断的病毒串
{
c[j] = a[k++];
if (k % strlen(a) == 0) k = 0;
}
if (BF(b, c, a) == 1)//用BF算法判断,病毒串为子串,DNA为母串
{
flag = 1;
break;
}
else
flag = 0;
}
if (flag == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
遇到问题有:
1、BF算法中子串长度用病毒长度
2、strlen函数用头文件<string.h>才能过
3、主函数中BF==1后,break跳出循环
推荐阅读
-
利用BF算法进行病毒检测的方法探析
-
ssh工作流程及原理-SSH(Secure Shell Protocol,安全的壳程序协议),它可以通过数据包加密技术将等待传输的数据包加密后再传输到网络上。ssh协议本身提供两个服务器功能:一个是类似telnet的远程连接使用shell的服务器;另一个就是类似ftp服务的sftp-server,提供更安全的ftp服务。 连接加密技术简介 目前常见的网络数据包加密技术通常是通过“非对称密钥系统”来处理的。主要通过两把不一样的公钥与私钥来进行加密与解密的过程。 公钥(public key):提供给远程主机进行数据加密的行为,所有人都可获得你的公钥来将数据加密。 私钥(private key):远程主机使用你的公钥加密的数据,在本地端就能够使用私钥来进行解密。私钥只有自己拥有。 SSH工作过程:在整个通讯过程中,为实现SSH的安全连接,服务端与客户端要经历如下五个阶段: 版本号协商阶段 SSH目前包括SSH1和SSH2两个版本,双方通过版本协商确定使用的版本 密钥和算法协商阶段 SSH支持多种加密算法,双方根据本端和对端支持的算法,协商出最终使用的算法 认证阶段 SSH客户端向服务器端发起认证请求,服务器端对客户端进行认证 会话请求阶段 认证通过后,客户端向服务器端发送会话请求 交互会话阶段 会话请求通过后,服务器端和客户端进行信息的交互 一、版本协商阶段 服务器端打开端口22,等待客户端连接; 客户端向服务器端发起TCP初始连接请求,TCP连接建立后,服务器向客户端发送第一个报文,包括版本标志字符串,格式为“SSH-<主协议版本号>.<次协议版本号>.<软件版本号>”,协议版本号由主版本号和次版本号组成,软件版本号主要是为调试使用。 客户端收到报文后,解析该数据包,如果服务器的协议版本号比自己的低,且客户端能支持服务器端的低版本,就使用服务器端的低版本协议号,否则使用自己的协议版本号。 客户端回应服务器一个报文,包含了客户端决定使用的协议版本号。服务器比较客户端发来的版本号,决定是否能同客户端一起工作。如果协商成功,则进入密钥和算法协商阶段,否则服务器断开TCP连接。 说明:上述报文都是采用明文方式传输。 二、密钥和算法协商阶段 服务器端和客户端分别发送算法协商报文给对端,报文中包含自己支持的公钥算法列表、加密算法列表、MAC(Message Authentication Code,消息验证码)算法列表、压缩算法列表等等。 服务器端和客户端根据对端和本端支持的算法列表得出最终使用的算法。 服务器端和客户端利用DH交换(Diffie-Hellman Exchange)算法、主机密钥对等参数,生成会话密钥和会话ID。 由此,服务器端和客户端就取得了相同的会话密钥和会话ID。对于后续传输的数据,两端都会使用会话密钥进行加密和解密,保证了数据传送的安全。在认证阶段,两端会使用会话用于认证过程。 会话密钥的生成: 客户端需要使用适当的客户端程序来请求连接服务器,服务器将服务器的公钥发送给客户端。(服务器的公钥产生过程:服务器每次启动sshd服务时,该服务会主动去找/etc/ssh/ssh_host*文件,若系统刚装完,由于没有这些公钥文件,因此sshd会主动去计算出这些需要的公钥文件,同时也会计算出服务器自己所需要的私钥文件。) 服务器生成会话ID,并将会话ID发给客户端。 若客户端第一次连接到此服务器,则会将服务器的公钥数据记录到客户端的用户主目录内的~/.ssh/known_hosts。若是已经记录过该服务器的公钥数据,则客户端会去比对此次接收到的与之前的记录是否有差异。客户端生成会话密钥,并用服务器的公钥加密后,发送给服务器。 ****服务器用自己的私钥将收到的数据解密,获得会话密钥。 服务器和客户端都知道了会话密钥,以后的传输都将被会话密钥加密。 三、认证阶段 SSH提供两种认证方法: 基于口令的认证(password认证):客户端向服务器发出password认证请求,将用户名和密码加密后发送给服务器,服务器将该信息解密后得到用户名和密码的明文,与设备上保存的用户名和密码进行比较,并返回认证成功或失败消息。 基于密钥的认证(publickey认证):客户端产生一对公共密钥,将公钥保存到将要登录的服务器上的那个账号的家目录的.ssh/authorized_keys文件中。认证阶段:客户端首先将公钥传给服务器端。服务器端收到公钥后会与本地该账号家目录下的authorized_keys中的公钥进行对比,如果不相同,则认证失败;否则服务端生成一段随机字符串,并先后用客户端公钥和会话密钥对其加密,发送给客户端。客户端收到后将解密后的随机字符串用会话密钥发送给服务器。如果发回的字符串与服务器端之前生成的一样,则认证通过,否则,认证失败。 注:服务器端对客户端进行认证,如果认证失败,则向客户端发送认证失败消息,其中包含可以再次认证的方法列表。客户端从认证方法列表中选取一种认证方法再次进行认证,该过程反复进行。直到认证成功或者认证次数达到上限,服务器关闭连接为止。实例
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
[姿势估计] 实践记录:使用 Dlib 和 mediapipe 进行人脸姿势估计 - 本文重点介绍方法 2):方法 1:基于深度学习的方法:。 基于深度学习的方法:基于深度学习的方法利用深度学习模型,如卷积神经网络(CNN)或递归神经网络(RNN),直接从人脸图像中学习姿势估计。这些方法能够学习更复杂的特征表征,并在大规模数据集上取得优异的性能。方法二:基于二维校准信息估计三维姿态信息(计算机视觉 PnP 问题)。 特征点定位:人脸姿态估计的第一步是通过特征点定位来检测和定位人脸的关键点,如眼睛、鼻子和嘴巴。这些关键点提供了人脸的局部结构信息,可用于后续的姿势估计。 旋转表示:常见的旋转表示方法包括欧拉角和旋转矩阵。欧拉角通过三个旋转角度(通常是俯仰、偏航和滚动)描述头部的旋转姿态。旋转矩阵是一个 3x3 矩阵,表示头部从一个坐标系到另一个坐标系的变换。 三维模型重建:根据特征点的定位结果,三维人脸模型可用于姿势估计。通过将人脸的二维图像映射到三维模型上,可以估算出人脸的旋转和平移信息。这就需要建立人脸的三维模型,然后通过优化方法将模型与特征点对齐,从而获得姿势估计结果。 特征点定位 特征点定位是用于检测人脸关键部位的五官基础部分,还有其他更多的特征点表示方法,大家可以参考我上一篇文章中介绍的特征点检测方案实践:人脸校正二次定位操作来解决人脸校正的问题,客户在检测关键点的代码上略有修改,坐标转换部分客户见上图 def get_face_info(image). img_copy = image.copy image.flags.writeable = False image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB) results = face_detection.process(image) # 在图像上绘制人脸检测注释。 image.flags.writeable = True image = cv2.cvtColor(image, cv2.COLOR_RGB2BGR) box_info, facial = None, None if results.detections: for detection in results. for detection in results.detections: mp_drawing.Drawing.detection = 无 mp_drawing.draw_detection(image, detection) 面部 = detection.location_data.relative_keypoints 返回面部 在上述代码中,返回的数据是五官(6 个关键点的坐标),这是用 mediapipe 库实现的,下面我们可以尝试用另一个库:dlib 来实现。 使用 dlib 使用 Dlib 库在 Python 中实现人脸关键点检测的步骤如下: 确保已安装 Dlib 库,可使用以下命令: pip install dlib 导入必要的库: 加载 Dlib 的人脸检测器和关键点检测器模型: 读取图像并将其灰度化: 使用人脸检测器检测图像中的人脸: 对检测到的人脸进行遍历,并使用关键点检测器检测人脸关键点: 显示绘制了关键点的图像: 以下代码将参数 landmarks_part 添加到要返回的关键点坐标中。