病毒感染检测:
医学研究者最近发现了某些新病毒，得知它们的DNA序列都是环状的。为了快速检测出患者是否感染了相应的病毒，研究者将患者的DNA和病毒的DNA均表示成一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。
例如，假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染。（人的DNA序列是线性的，病毒的DNA序列是环状的）
分析：
该案例实际上就是模式匹配问题，将患者的DNA序列作为主串，病毒的DNA序列作为模式串，特殊之处在于病毒的DNA序列是环状的。可用BF算法或KMP算法。
算法步骤：
（1）设置标志变量flag，用来标志是否匹配成功，初值为0表示未匹配；
（2）病毒DNA序列的长度是m，将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次，形成长度为2m的串V；
（3）对串V循环m次，重复执行以下操作：文章来源：https://www.toymoban.com/news/detail-718470.html
-
- 从V中依次取得每个长度为m的病毒DNA环状字符串，作为模式串T；
- 调用BF算法，将模式串T和主串S（患者的DNA序列）进行模式匹配，将匹配结果返回赋值给flag；
- 若flag非0，表示匹配成功，中止循环表明该患者感染了病毒。
代码如下：文章来源地址https://www.toymoban.com/news/detail-718470.html
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bd(char *T, char *S, int &len_T, int &len_S ) { //序列处理
printf("输入病毒串:");
gets(T);
printf("\n输入患者串:");
gets(S);
strcat(T, T); //病毒串序列展开 例:abb变为abbabb
len_T = strlen(T);
len_S = strlen(S);
}
int bf(char *V, char *S, int &len_S) { //bf算法
int i = 0, j = 0, len_V = 3;
while (i < len_S && j < len_V) {
if (S[i] == V[j]) { //判断环状病毒串和患者串字符是否匹配
i++;
j++;
} else {
i = i - j + 1; //患者串回退至不匹配字符的下一个
j = 0; //环状病毒串回退至开头
}
}
if (j == len_V) {
return 1;
} else {
return 0;
}
}
void Getnext(int *next, char *S, int &len_S) { //获取next数组
next[0] = -1; //next数组前两个固定赋值
next[1] = 0;
int i = 1; //i为患者串下标 j为环状病毒串下标
int j = 0;
while (i < len_S) {
if ((j == 0) || (S[i] == S[j])) {
i++;
j++;
next[i] = j; //next数组存储的值为j回退的字符数组的下标
} else {
j = next[j];
}
}
}
/*例
string: a b a b a a b
next: -1 0 1 1 2 3 1
sub: 0 1 2 3 4 5 6
*/
int kmp(char *V, char *S, int &len_S) { //kmp算法
int i = 0, j = 0, len_V = 3;
int *next = (int *)malloc(sizeof(int) * len_S); //申请空间
Getnext(next, S, len_S);
while (i < len_S && j < len_V) {
if ((j == -1) || (V[j] == S[i])) {
j++;
i++;
} else {
j = next[j]; //区别bf算法 回退位置不同 其他相同
}
}
free(next); //结束释放内存
if (j == len_V) {
return 1;
} else {
return 0;
}
}
void xh(int len_S, int len_T, char *T, char *S) { //检测函数
int flag;
len_T /= 2;
while (len_T ) {
char V[3]; //环状病毒串
strncpy(V, T, 3); //例:abb有三个环状病毒串abb、bba、bab
//二选一 bf&kmp
// flag = bf(V, S, len_S); //使用bf算法
flag = kmp(V, S, len_S); //使用kmp算法
if (flag) { //判断
printf("感染\n");
return ;
}
T++ ;
len_T--;
}
printf("未感染\n");
}
int main(void) {
char T[30], S[30]; //病毒串T 患者串S
int len_T, len_S; //串长度
bd(T, S, len_T, len_S);
xh(len_S, len_T, T, S);
}到了这里，关于(C语言)数据结构算法-病毒感染检测(BF算法&&KMP算法)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
