(C语言)数据结构算法-病毒感染检测(BF算法&&KMP算法)

病毒感染检测:

医学研究者最近发现了某些新病毒，得知它们的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次，重复执行以下操作：

1. 1. 从V中依次取得每个长度为m的病毒DNA环状字符串，作为模式串T；
   2. 调用BF算法，将模式串T和主串S（患者的DNA序列）进行模式匹配，将匹配结果返回赋值给flag；
   3. 若flag非0，表示匹配成功，中止循环表明该患者感染了病毒。

代码如下：

#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);
}