病毒感染檢測(cè):
醫(yī)學(xué)研究者最近發(fā)現(xiàn)了某些新病毒，得知它們的DNA序列都是環(huán)狀的。為了快速檢測(cè)出患者是否感染了相應(yīng)的病毒，研究者將患者的DNA和病毒的DNA均表示成一些字母組成的字符串序列，然后檢測(cè)某種病毒DNA序列是否在患者的DNA序列中出現(xiàn)過(guò)，如果出現(xiàn)過(guò)，則此人感染了該病毒，否則沒(méi)有感染。
例如，假設(shè)病毒的DNA序列為baa，患者1的DNA序列為aaabbba，則感染，患者2的DNA序列為babbba，則未感染。（人的DNA序列是線性的，病毒的DNA序列是環(huán)狀的）
分析：
該案例實(shí)際上就是模式匹配問(wèn)題，將患者的DNA序列作為主串，病毒的DNA序列作為模式串，特殊之處在于病毒的DNA序列是環(huán)狀的?？捎肂F算法或KMP算法。
算法步驟：
（1）設(shè)置標(biāo)志變量flag，用來(lái)標(biāo)志是否匹配成功，初值為0表示未匹配；
（2）病毒DNA序列的長(zhǎng)度是m，將存儲(chǔ)病毒DNA序列的字符串長(zhǎng)度擴(kuò)大為2m，將病毒DNA序列連續(xù)存儲(chǔ)兩次，形成長(zhǎng)度為2m的串V；
（3）對(duì)串V循環(huán)m次，重復(fù)執(zhí)行以下操作：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-718470.html
-
- 從V中依次取得每個(gè)長(zhǎng)度為m的病毒DNA環(huán)狀字符串，作為模式串T；
- 調(diào)用BF算法，將模式串T和主串S（患者的DNA序列）進(jìn)行模式匹配，將匹配結(jié)果返回賦值給flag；
- 若flag非0，表示匹配成功，中止循環(huán)表明該患者感染了病毒。
代碼如下：文章來(lái)源地址http://www.zghlxwxcb.cn/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); //病毒串序列展開(kāi) 例:abb變?yōu)閍bbabb
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]) { //判斷環(huán)狀病毒串和患者串字符是否匹配
i++;
j++;
} else {
i = i - j + 1; //患者串回退至不匹配字符的下一個(gè)
j = 0; //環(huán)狀病毒串回退至開(kāi)頭
}
}
if (j == len_V) {
return 1;
} else {
return 0;
}
}
void Getnext(int *next, char *S, int &len_S) { //獲取next數(shù)組
next[0] = -1; //next數(shù)組前兩個(gè)固定賦值
next[1] = 0;
int i = 1; //i為患者串下標(biāo) j為環(huán)狀病毒串下標(biāo)
int j = 0;
while (i < len_S) {
if ((j == 0) || (S[i] == S[j])) {
i++;
j++;
next[i] = j; //next數(shù)組存儲(chǔ)的值為j回退的字符數(shù)組的下標(biāo)
} 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); //申請(qǐng)空間
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]; //區(qū)別bf算法 回退位置不同 其他相同
}
}
free(next); //結(jié)束釋放內(nèi)存
if (j == len_V) {
return 1;
} else {
return 0;
}
}
void xh(int len_S, int len_T, char *T, char *S) { //檢測(cè)函數(shù)
int flag;
len_T /= 2;
while (len_T ) {
char V[3]; //環(huán)狀病毒串
strncpy(V, T, 3); //例:abb有三個(gè)環(huán)狀病毒串a(chǎn)bb、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; //串長(zhǎng)度
bd(T, S, len_T, len_S);
xh(len_S, len_T, T, S);
}到了這里，關(guān)于(C語(yǔ)言)數(shù)據(jù)結(jié)構(gòu)算法-病毒感染檢測(cè)(BF算法&&KMP算法)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
