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()
  

1. int virus_dna_extend(char virus_src[], char virus_dst[][DNA_SIZE_MAX], int *num_of_virus)
2. {
3.         int virus_len = strlen(virus_src);
4.         int i = virus_len;
5.         int idx = 0;
6.         char *temp = (char *)malloc(2* DNA_SIZE_MAX *sizeof(char));
7.         if (temp == NULL)
8.                 return OVERFLOW;
9.         memset(temp, 0, (2 * virus_len + 1) * sizeof(char));
10.         memcpy(temp, virus_src, virus_len);
12.         for (int j = 0; j < virus_len; j++)
13.         {
14.                 temp[i++] = temp[j];
15.         }
16.         temp[2 * virus_len + 1] = '\0';
17.         //printf("%s\n", temp);
19.         for (int i = 0; i < virus_len; i++)
20.         {
21.                 for (int j = 0; j < virus_len; j++)
22.                 {
23.                         virus_dst[idx][j] = temp[i + j];
24.                 }
25.                 virus_dst[idx][virus_len + 1] = '\0';
26.                 //printf("%s\n", virus_dst[idx]);
27.                 idx++;
28.         }
29.         *num_of_virus = idx;
30.         free(temp);
31.         return 0;
32. }

复制代码

• 函数：virus_detect()
  

1. int virus_detect(const char *person_dna, const char virus_dna[][DNA_SIZE_MAX], int num_of_virus)
2. {
3.         int result = FALSE;
4.         for (int i = 0; i < num_of_virus; i++)
5.         {
6.                 if (-1 != index_bf(person_dna, virus_dna[i], 0))
7.                 {
8.                         result = TRUE;
9.                         break;
10.                 }
11.         }
12.         return result;
13. }

复制代码

• 函数：main()
  

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. #define FALSE    0
6. #define TRUE     1
7. #define OVERFLOW 2
9. int main(void)
10. {
11.         char person_dna[10][DNA_SIZE_MAX] = {
12.                 "bbaabbba",
13.                 "aaabbbba",
14.                 "abceaabb",
15.                 "abaabcea",
16.                 "cdabbbab",
17.                 "cabbbbab",
18.                 "bcdedbda",
19.                 "bdedbcda",
20.                 "cdcdcdec",
21.                 "cdccdcce"
22.         };
23.         char virus_dna[10][2 * DNA_SIZE_MAX + 1] = {
24.                 "baa",
25.                 "baa",
26.                 "aabb",
27.                 "aabb",
28.                 "abcd",
29.                 "abcd",
30.                 "abcde",
31.                 "acc",
32.                 "cde",
33.                 "cced"
34.         };
36.         printf("病毒DNA              "
37.                    "患者DNA              "
38.                    "检测结果             \n");
39.         for (int i = 0; i < 10; i++)
40.         {
41.                 char vir_dst[100][DNA_SIZE_MAX] = { 0 };
42.                 const char *negative = "NO";
43.                 const char *positive = "YES";
44.                 int num_of_vir = 0;
45.                 virus_dna_extend(virus_dna[i], vir_dst, &num_of_vir);
46.                 int result = virus_detect(person_dna[i], vir_dst, num_of_vir);
48.                 if (result == TRUE)
49.                         printf("%-20s %-20s %-20s\n", virus_dna[i], person_dna[i], positive);
50.                 else
51.                         printf("%-20s %-20s %-20s\n", virus_dna[i], person_dna[i], negative);
52.         }
53.         return 0;
54. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！