BF算法的实现：病毒感染检测

一、问题引入

BF（Brute-Force）算法介绍了BF算法的具体实现，但并未结合具体案例。

本随笔就是结合案例（病毒感染检测）对BF算法进行结合分析。

案例4.1: 病毒感染检测

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

二、解决过程

• 函数：virus_dna_extend()

int virus_dna_extend(char virus_src[], char virus_dst[][DNA_SIZE_MAX], int *num_of_virus)
{
	int virus_len = strlen(virus_src);
	int i = virus_len;
	int idx = 0;
	char *temp = (char *)malloc((2 * DNA_SIZE_MAX + 1) *sizeof(char));
	if (temp == NULL)
		return OVERFLOW;
	memset(temp, 0, (2 * DNA_SIZE_MAX + 1) * sizeof(char));
	memcpy(temp, virus_src, virus_len);

	for (int j = 0; j < virus_len; j++)
	{
		temp[i++] = temp[j];
	}
	temp[2 * virus_len + 1] = '\0';
	//printf("%s\n", temp);

	for (int i = 0; i < virus_len; i++)
	{
		for (int j = 0; j < virus_len; j++)
		{
			virus_dst[idx][j] = temp[i + j];
		}
		virus_dst[idx][virus_len + 1] = '\0';
		//printf("%s\n", virus_dst[idx]);
		idx++;
	}
	*num_of_virus = idx;
	free(temp);
	return 0;
}

• 函数：virus_detect()

int virus_detect(const char *person_dna, const char virus_dna[][DNA_SIZE_MAX], int num_of_virus)
{
	int result = FALSE;
	for (int i = 0; i < num_of_virus; i++)
	{
		if (-1 != index_bf(person_dna, virus_dna[i], 0))
		{
			result = TRUE;
			break;
		}
	}
	return result;
}

• 函数：main()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FALSE    0
#define TRUE     1
#define OVERFLOW 2

int main(void)
{
	char person_dna[10][DNA_SIZE_MAX] = {
		"bbaabbba",
		"aaabbbba",
		"abceaabb",
		"abaabcea",
		"cdabbbab",
		"cabbbbab",
		"bcdedbda",
		"bdedbcda",
		"cdcdcdec",
		"cdccdcce"
	};
	char virus_dna[10][2 * DNA_SIZE_MAX + 1] = {
		"baa",
		"baa",
		"aabb",
		"aabb",
		"abcd",
		"abcd",
		"abcde",
		"acc",
		"cde",
		"cced"
	};

	printf("病毒DNA              "
		   "患者DNA              "
		   "检测结果             \n");
	for (int i = 0; i < 10; i++)
	{
		char vir_dst[100][DNA_SIZE_MAX] = { 0 };
		const char *negative = "NO";
		const char *positive = "YES";
		int num_of_vir = 0;
		virus_dna_extend(virus_dna[i], vir_dst, &num_of_vir);
		int result = virus_detect(person_dna[i], vir_dst, num_of_vir);

		if (result == TRUE)
			printf("%-20s %-20s %-20s\n", virus_dna[i], person_dna[i], positive);
		else
			printf("%-20s %-20s %-20s\n", virus_dna[i], person_dna[i], negative);
	}
	return 0;
}

? 运行结果

三、反思总结

重点理解病毒DNA的扩展函数，至于BF算法函数请参考BF（Brute-Force）算法

例如：病毒DNA的序列是 abb ，由于它可以形成环结构，那么它的组成有 abb 、 bba、 bab。

如何分析得到病毒DNA所有可能性呢？

• 第一步：扩展病毒DNA长度 ，例如 abbabb

	int virus_len = strlen(virus_src);
	int i = virus_len;
	char *temp = (char *)malloc(2* DNA_SIZE_MAX *sizeof(char));
	memset(temp, 0, (2 * virus_len + 1) * sizeof(char));
	memcpy(temp, virus_src, virus_len);

	for (int j = 0; j < virus_len; j++)
	{
		temp[i++] = temp[j];
	}
	temp[2 * virus_len + 1] = '\0';

• 第二步：解析DNA的可能性，每次读三个字符，下一轮的读取开始位置是上一轮的开始位置+1

	for (int i = 0; i < virus_len; i++)
	{
		for (int j = 0; j < virus_len; j++)
		{
			virus_dst[idx][j] = temp[i + j];
		}
		virus_dst[idx][virus_len + 1] = '\0';
		idx++;
	}

四、参考引用

数据结构第二版：C语言版

原文链接：https://www.cnblogs.com/caojun97/p/17294920.html