#include<iostream>#include<fstream>#include<string.h>#include<utility>using namespace std;typedef struct{char ch[600]; //若是非空串,则按串长分配存储区,否则ch为NULLint len; //串长度} HString;int Index_BF(HString Virus,HString Person,int V,int P)//V ,P分别为病毒的长度,和患者DNA长度 {int i=0,j=0;//初始化,从第0个位置开始 while(i<V&&j<P)// 两个序列均未到达结尾 {if(Virus.ch[i]==Person.ch[j])//相同,继续往后比较 {++i;++j;}else //不相同,重新匹配 {j=j-i+1;i=0;//患者序列的下一个,病毒序列第一个 }}if(i==V) return 1;//匹配成功 else return 0;//匹配失败 }
int check(HString &Virus,HString &Person,int V,int P)
//V ,P分别为病毒的长度,和患者DNA长度 {HString temp;//中转辅助串temp,记录病毒的各种不同序列 int flag=0;// 作为判断元素 for(int i=V,j=0;j<V;j++)Virus.ch[i++]=Virus.ch[j];//将病毒DNA储存两次 Virus.ch[2*V]='\0';//添加结束符号 for(int i=0;i<V;i++)//依次取得每个长度为V的病毒DNA环状字符串 {for(int j=0;j<V;j++){temp.ch[j]=Virus.ch[i+j];}temp.ch[Virus.len]='\0';//添加结束符 flag=Index_BF(temp,Person,V,P);//模式匹配 if(flag)break;//匹配成功,退出循环 }if(flag)return 1;//匹配成功else return 0;//匹配失败 }void Virus_detection(){char Vir[600];//用来存放病毒DNA序列 int num,f=0; //用来记录有几组匹配数据HString Virus,Person,temp; //主串Person,模式串Virus,中转辅助串tempifstream inFile("病毒感染检测输入数据.txt"); //设置输入文件地址,文件要在同级目录保存ofstream outFile("病毒感染检测输出结果.txt");//设置输出文件地址(也可以屏幕输出)inFile>>num; //读取待检测的任务数while(num--) //依次检测每对病毒DNA和人的DNA是否匹配{inFile >> Virus.ch >> Person.ch;//读取病毒和人的DNA strcpy(Vir,Virus.ch);//将病毒DNA储存在Vir中,用于输出 Virus.len = strlen(Virus.ch);//求病毒DNA长度 Person.len = strlen(Person.ch);//求人DNA长度 f=check(Virus,Person,Virus.len,Person.len);//检测是否匹配 if(f) cout<<Vir<<" "<<Person.ch<<" "<<"YES"<<endl;//匹配输出YES else cout<<Vir<<" "<<Person.ch<<" "<<"NO"<<endl;//不匹配输出NO }}int main(){Virus_detection();return 0;}