實驗四 基于字符串模式匹配算法的病毒感染檢測

【實驗目的】
1.掌握字符串的順序存儲表示方法。
2.掌握字符串模式匹配BF算法和KMP算法的實現(xiàn)。
【實驗內(nèi)容】
問題描述
醫(yī)學研究者最近發(fā)現(xiàn)了某些新病毒,通過對這些病毒的分析,得知它們的DNA序列都是環(huán)狀的。現(xiàn)在研究者已收集了大量的病毒DNA和人的DNA數(shù)據(jù),想快速檢測出這些人是否感染了相應的病毒。為了方便研究,研究者將人的DNA和病毒DNA均表示成由一些字母組成的字符序列,然后檢測某種病毒DNA序列是否在患者的DNA序列中出現(xiàn)過。如果出現(xiàn)過,則此人感染了該病毒,否則沒有感染。例如,假設病毒的DNA序列為baa，患者1的DNA序列為aaabbba，則感染;患者2的DNA序列為babbba,則未感染。(注意,人的DNA序列是線性的,而病毒的DNA序列是環(huán)狀的。)
輸入要求
多組數(shù)據(jù),每組數(shù)據(jù)有1行,為序列A和B,A對應病毒的DNA序列,B對應人的DNA序列。A和B都為“0”時輸入結(jié)束。
輸入樣例
abbab abbabaab
baa cacdvcabacsd
abc def
0 0
輸出樣例
YES
YES
NO
【實驗提示】
此實驗內(nèi)容即要求實現(xiàn)教材算法的具體案例。利用BF算法來實現(xiàn)字符串的模式匹配過程的,效率較低,。利用KMP算法完成模式匹配以提高算法的效率。

解決方法1：暴力算法

#include <stdio.h> // printf(); scanf() #include <stdlib.h> // exit() #include <malloc.h> // malloc() #include <time.h> // srand((unsigned)time(NULL)); #include <string.h>#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0typedef int Status;typedef int ElemType;#define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN + 1]; Status StrAssign(SString &T, char *chars) {if(strlen(chars) > MAXSTRLEN)return ERROR;else {T[0] = strlen(chars); for(int i=1; i<=T[0]; i++)T[i] = *(chars+i-1);return OK;} }Status StrCopy(SString &T, SString S) {for(int i=0; i<=S[0]; i++)T[i] = S[i];return OK; }int StrLength(SString S) {return S[0]; }int index(SString S,SString T,int pos) {int i=pos,j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else {i=i-j+2;j=1;}}if(j>T[0])return i-T[0];else return 0;} int main() { int flag[100];int w=0; int x;int number;int pos;char c[MAXSTRLEN+1],d[MAXSTRLEN+1];SString S;SString T;SString Z;do{scanf("%s",c);scanf("%s",d);StrAssign(S, c);StrAssign(T, d);char str[T[0]];for(int i=0; i<=S[0]; i++)str[i] = T[i+1];int i=0;Z[0]=T[0];for(i=0;i<T[0];i++){for(int j=1;j<=T[0];j++){Z[j]=str[(j+i)%(T[0])]; }number=index(S,Z,pos);if(number!=0&&strcmp(c,"0")!=0&&strcmp(d,"0")!=0){flag[w++]=1;break; } }if(i==T[0]&&strcmp(c,"0")!=0&&strcmp(d,"0")!=0)flag[w++]=0;}while(strcmp(c,"0")!=0&&strcmp(d,"0")!=0);for(int e=0;e<w;e++){if(flag[e]==1)printf("YES\n");//即在人體dna中找到與病毒dna相同的序列 elseprintf("NO\n");//即在人體dna中找到與病毒dna相同的序列 } return 0;}

解決方法2：kmp算法

#include <stdio.h> // printf(); scanf() #include <stdlib.h> // exit() #include <malloc.h> // malloc() #include <time.h> // srand((unsigned)time(NULL)); #include <string.h>#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0typedef int Status; typedef int ElemType; #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN + 1];Status StrAssign(SString &T, char *chars) {if(strlen(chars) > MAXSTRLEN)return ERROR;else {T[0] = strlen(chars); // 0號單元存放串的長度for(int i=1; i<=T[0]; i++)T[i] = *(chars+i-1);return OK;} }Status StrCopy(SString &T, SString S) {for(int i=0; i<=S[0]; i++)T[i] = S[i];return OK; }int StrLength(SString S) {return S[0]; }void get_next(SString T,int next[]) {int j; int i=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;next[i]=j;}else j=next[j];} }int Index_KMP(SString S,SString T,int pos) { int next[MAXSTRLEN+1]; get_next(T,next);int i=pos; int j=1;while(i<=S[0]&&j<=T[0])//i j都不超過其串的長度{//失配 //1：失配，當j==0時，則目標主串的檢測指針前進一位，模式串檢測指針回到T[1].進行下一趟的比較//2：失配，當j>0時，那么在下一趟比較時，模式串的起始位置為Tnext[j],目標主串S的檢測指針不回溯，仍然指向上一趟失配的位置 if(j==0||S[i]==T[j]){++i;++j;//繼續(xù)比較后繼字符 }else j=next[j];//模式串向右移動 }if(j>T[0]) return i-T[0];//匹配成功 else return 0; }int main() { int flag[100];int w=0; int x;int number;int pos;char c[MAXSTRLEN+1],d[MAXSTRLEN+1];SString S;SString T;SString Z;do{scanf("%s",d); scanf("%s",c);StrAssign(S, c);StrAssign(T, d);char str[T[0]];for(int i=0; i<=S[0]; i++)str[i] = T[i+1];int i=0;Z[0]=T[0];for(i=0;i<T[0];i++){for(int j=1;j<=T[0];j++){Z[j]=str[(j+i)%(T[0])]; }//StrPrint(Z); //printf("\n");number=Index_KMP(S,Z,pos);if(number!=0&&strcmp(c,"0")!=0&&strcmp(d,"0")!=0){flag[w++]=1;break; } }if(i==T[0]&&strcmp(c,"0")!=0&&strcmp(d,"0")!=0)flag[w++]=0;}while(strcmp(c,"0")!=0&&strcmp(d,"0")!=0);for(int e=0;e<w;e++){if(flag[e]==1)printf("YES\n");//即在人體dna中找到與病毒dna相同的序列 elseprintf("NO\n");//即在人體dna中找到與病毒dna相同的序列 } return 0;} 解決方法3：kmp算法改進版```c #include <stdio.h> // printf(); scanf() #include <stdlib.h> // exit() #include <malloc.h> // malloc() #include <time.h> // srand((unsigned)time(NULL)); #include <string.h>#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN + 1]; Status StrAssign(SString &T, char *chars) {if(strlen(chars) > MAXSTRLEN)return ERROR;else {T[0] = strlen(chars); for(int i=1; i<=T[0]; i++)T[i] = *(chars+i-1);return OK;} }int StrLength(SString S) {return S[0]; }void get_nextval(SString T,int nextval[]) {int j; int i=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;if(T[i]!=T[j])nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];} }int Index_KMP_val(SString S,SString T,int pos) { int nextval[MAXSTRLEN+1]; get_nextval(T,nextval);int i=pos; int j=1;while(i<=S[0]&&j<=T[0])//i j都不超過其串的長度{//失配 //1：失配，當j==0時，則目標主串的檢測指針前進一位，模式串檢測指針回到T[1].進行下一趟的比較//2：失配，當j>0時，那么在下一趟比較時，模式串的起始位置為Tnext[j],目標主串S的檢測指針不回溯，仍然指向上一趟失配的位置 if(j==0||S[i]==T[j]){++i;++j;//繼續(xù)比較后繼字符 }else j=nextval[j];//模式串向右移動 }if(j>T[0]) return i-T[0];//匹配成功 else return 0; }int main() { int flag[100];//用于計算循環(huán)數(shù)組 每次的結(jié)果 int w=0; //用于統(tǒng)計flag數(shù)組 int x;int number;int pos;char c[MAXSTRLEN+1],d[MAXSTRLEN+1];SString S;SString T;SString Z;do{scanf("%s",d); scanf("%s",c);StrAssign(S, c);StrAssign(T, d);char str[T[0]];for(int i=0; i<=S[0]; i++)str[i] = T[i+1];int i=0;Z[0]=T[0];for(i=0;i<T[0];i++){for(int j=1;j<=T[0];j++){Z[j]=str[(j+i)%(T[0])]; }number=Index_KMP_val(S,Z,pos);if(number!=0&&strcmp(c,"0")!=0&&strcmp(d,"0")!=0){flag[w++]=1;break; } }if(i==T[0]&&strcmp(c,"0")!=0&&strcmp(d,"0")!=0)flag[w++]=0;}while(strcmp(c,"0")!=0&&strcmp(d,"0")!=0);for(int e=0;e<w;e++){if(flag[e]==1)printf("YES\n");//即在人體dna中找到與病毒dna相同的序列 elseprintf("NO\n");//即在人體dna中找到與病毒dna相同的序列 } return 0;}

總結(jié)

以上是生活随笔為你收集整理的数据结构——基于字符串模式匹配算法的病毒感染检测的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。