病毒感染检测:

医学研究者最近发现了某些新病毒，得知它们的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. 从V中依次取得每个长度为m的病毒DNA环状字符串，作为模式串T；
    2. 调用BF算法，将模式串T和主串S（患者的DNA序列）进行模式匹配，将匹配结果返回赋值给flag；
    3. 若flag非0，表示匹配成功，中止循环表明该患者感染了病毒。

代码如下：

#include #include #include void bd(char *T, char *S, int &len_T, int &len_S ) {//序列处理printf("输入病毒串:");gets(T);printf("\n输入患者串:");gets(S);strcat(T, T);//病毒串序列展开 例:abb变为abbabblen_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 bnext:-1 0 1 1 2 3 1sub: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 患者串Sint len_T, len_S;//串长度bd(T, S, len_T, len_S);xh(len_S, len_T, T, S);}