@TOC

一、Chapter One【实验题目】

1.【实验目的】

1．掌握字符串的顺序存储表示方法。2．掌握字符串模式匹配算法 BF 算法或 KMP 算法的实现。

2.【实验内容】

问题描述医学研究者最近发现了某些新病毒，通过对这些病毒的分析，得知它们的 DNA 序列都是环状的。现在研究者已收集了大量的病毒 DNA 和人的 DNA 数据，想快速检测出这些人是否感染了相应的病毒。为了方便研究，研究者将人的 DNA 和病毒 DNA 均表示成由一些字母组成的字符串序列，然后检测某种病毒 DNA 序列是否在患者的 DNA 序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。例如，假设病毒的 DNA 序列为 baa，患者 1 的 DNA 序列为 aaabbba,则感染;患者 2 的 DNA 序列为 babbba，则未感染。(注意：人的 DNA 序列是线性的，而病毒的 DNA 序列是环状的。)

输入要求多组数据，每组数据有 1 行，为序列 A 和 B，A 对应病毒的 DNA 序列，B 对应人的 DNA 序列。A 和 B 都为“0”时输入结束。输出要求对于每组数据输出 1 行，若患者感染了病毒输出“YES"”，否则输出“NO”。输人样例

abbab abbabaabbaa cacdvcabacsdabc def0 0

输出样例

YESYESNO

3.【实验提示】

此实验内容即要求实现主教材的案例 4.1，具体实现可参考算法 4.5。算法 4.5 是利用 BF 算法来实现字符串的模式匹配过程的，效率较低，可以利用 KMP 算法完成模式匹配以提高算法的效率。读者可以模仿算法 4.5，利用 KMP 算法来完成病毒感染检测的方案。

二、Chapter Two【实验分析】

1.实验整体思路：

在本题中，我们采用 BF 算法来实现对病毒检测问题的描述，本程序的难点是如何找出病毒 DNA 环状字符串的所有展开字符串。原理：首先要传递参数到 int judge 函数中，将字符串长度为 n 的病毒 DNA 扩展为长度为 2n 的字符串，再用双重循环输出长度为 m 的病毒展开字符串。调用 BF 函数进行模式匹配，返回判断结果到主函数中。虑到程序需要输入输出多组数据，有两种方法可以实现：1、用二维数组进行字符串存储，并且同时进行字符串匹配，并将匹配结果输出。2、程序使用一维数组存储，在输入完一组数据后存储在缓存区内，然后将判断结果存入数组 s 中，最后根据数组 s 统一输出判断结果。本程序使用方法二。

实验详细步骤：

2.数据结构定义

定义全局变量数组 V,D。char V[20]; //病毒 DNA 数组 char D[20]; //人的 DNA 数组定义标识符 YES 为 1，标识符 NO 为 0#define YES 1#define NO 0

3.主要功能模块设计

（1）int BFjudge()函数：找出病毒 DNA 环状字符串的所有展开字符串，char D, char V：形参 D 是数组 D，形参 V 是数组 V。（2）int BF()函数：利用 BF 算法进行模式匹配 char D, char ：形参 D 是数组 D，形参 V 是环状字符串的展开字符串。（3）int PRINThand()函数：输入多组数据，每输入一组数据就将匹配结果存进数组 s 中，最后统一输出检测结果。

4.主要步骤描述

（1）首先引用我们的头文件和需要的全局变量；（2）然后用模式匹配函数 BF，进行模式匹配；（3）使用循环展开函数，将字符串长度为 m 的病毒 DNA 扩展为长度为 2m 的字符串；（4）再创建输入函数，输入病毒 DNA 及人的 DNA，程序使用一维数组存储，在输入完一组数据后存储在缓存区内，然后将判断结果存入数组 s 中，最后根据数组 s 统一输出判断结果。；（5）最后通过主函数，调用我们之前已经构建好的函数，实现我们的判断功能，将结果进行输出。

三、Chapter Three【运行截图】

四、Chapter Four【源码详析】

#include <stdio.h> //头文件 #include<iostream>#include <string.h>#define _CRT_SECURE_NO_WARNINGS#define YES 1#define NO  0
//全局变量部分char V[20];  //病毒DNA字符串char D[20];  //人的DNA字符串

//主要功能函数的具体实现及说明//模式匹配函数(BF)int BF(char *D, char *V){  //用BF算法进行模式匹配    int i=0,j=0;    while (i<strlen(D) && j<strlen(V)){    if (D[i]==V[j])     {        i++; j++;}      else      {             i = i-j+1;             j = 0;      }}    if (j>=strlen(V)) return YES;    else return NO;}
//循环展开函数（BFjudge）int BFjudge(char *D, char *V){  int flag = 0;  int i,j,m;  char temp[20];   m = strlen(V);  for(i=m,j=0;j<m;j++)  V[i++]=V[j];   V[2*m] = '\0';  //将字符串长度为m的病毒DNA扩展为长度为2m的字符串    for(i=0; ;i++)  {      for(j=0;j<m;j++)    temp[j] = V[i+j];         temp[m] = '\0';  //循环展开环状病毒DNA      flag = BF(D,temp);  //调用BF模块进行模式匹配      if (flag) break;      else if (i>=m) return NO;  //所有展开字符串均匹配失败      else continue;   }    return YES;}
// 程序使用一维数组存储，在输入完一组数据后存储在缓存区内，// 然后将判断结果存入数组s中，最后根据数组s统一输出判断结果。 int PRINThand(){  FILE *fp1,*fp2;    int i=0,k=0;    int s[20]; 
    printf("\n请输入病毒DNA及人的DNA（输入0 0结束）：\n");  while(1)    {                 scanf("%s", &V[i]);      scanf("%s", &D[i]);        if(V[i]=='0' && D[i]=='0') break;              if(BFjudge(D, V)==1)   s[k]=1;    else   s[k]=0;    k++;    }  printf("病毒感染检测输出结果：\n");  for(k=0;s[k]<2;k++)  {    if(s[k]==1)  printf("YES\n");      else  printf("NO\n");  }     return 0; }  //主函数int main(){  int key = 0, Num;  while(1)  {  printf("欢迎使用病毒感染检测系统\n");  PRINThand(); break;  }}