基于串匹配方法的文档复制检测系统研究,基于字符串模式匹配算法的病毒感染检测问题实验报告
Yyds干货库存
@TOC
第一章【实验题目】
1.[实验目的]
1.掌握字符串的顺序存储表示。
2.掌握字符串模式匹配算法BF算法或KMP算法的实现。
2.[实验内容]
问题描述
医学研究人员最近发现了一些新病毒。通过对这些病毒的分析，我们知道它们的DNA序列都是环状的。现在研究人员收集了大量的病毒DNA和人类DNA数据，想快速检测这些人是否感染了相应的病毒。为了研究方便，研究人员将人类DNA和病毒DNA表示为由一些字母组成的字符串序列，然后检测患者的DNA序列中是否出现过病毒DNA序列。如果有，这个人就感染了病毒，否则，他就没有被感染。例如，假设病毒的DNA序列是baa，而患者1的
如果DNA序列是aaabbba，就会被感染；2号病人的DNA序列是babbba，但是没有被感染。(注：人类
DNA序列是线性的，而病毒DNA序列是环状的。)
投入物需要量
多组数据，每组一行，是序列A和B，A对应病毒的DNA序列，B对应人的DNA序列。当A和B都为“0”时，输入结束。
输出要求
对于每组数据，输出一行，如果患者感染了病毒，则输出“是”，否则输出“否”。
输入样本
阿巴布
baa cacdvcabacsd
abc定义
0 0
输出样本
是
不
3.【实验小贴士】
这个实验内容是主教材的案例4.1，具体实现可以参考算法4.5。算法4.5使用BF算法实现字符串的模式匹配过程，效率较低。KMP算法可以用来完成模式匹配，提高算法的效率。读者可以模仿算法4.5，使用KMP算法来完成病毒感染检测方案。
二、第二章【实验分析】
1.实验的总体思路是：
在本课题中，我们使用BF算法来描述病毒检测问题。这个程序的难点是如何找出病毒DNA环串的所有扩展串。原理：首先要将参数传递给int judge函数，将长度为n的病毒DNA扩展成长度为2n的字符串，然后通过双循环输出长度为m的病毒。调用BF函数进行模式匹配，并将判断结果返回给main函数。
考虑到程序需要输入输出多组数据，有两种实现方式：1。用二维数组存储字符串，同时匹配字符串，输出匹配结果。2.该程序使用一维数组存储。输入一组数据后，存放在缓存区，然后将判断结果存放在数组s中，最后根据数组s统一输出判断结果，使用本程序的方法2。
详细的实验步骤：
2.数据结构的定义
定义全局变量数组V，d。
char V[20]；//病毒DNA阵列
char D[20]；//人的DNA数组
是定义为1，否定义为0。
#定义是1
#定义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)最后通过main函数，调用我们之前构建的函数，实现我们的判断函数，输出结果。
三。第三章【跑步截图】
第四章【源代码详细分析】
# includes dio . h//头文件
#包括iostream
#包含字符串. h
#define _CRT_SECURE_NO_WARNINGS
#定义是1
#定义0号
//全局变量部分
char V[20]；//病毒DNA字符串
char D[20]；//人类DNA字符串
//主要功能的具体实现和描述
//模式匹配功能(BF)
int BF(字符D，字符V)
{//使用BF算法进行模式匹配
int i=0，j=0；
while (i strlen(D) j strlen(V))
if (D[i]==V[j])
我；j；
其他
I=I-j 1；
j=0；
if (j=strlen(V))返回YES
否则返回否；
//循环展开函数(BFjudge)
int BFjudge(char *D，char *V)
int flag=0；
int i，j，m；
充电温度[20]；
m=strlen(V)；
for(i=m，j=0；j j)V[I]=V[j]；
v[2 * m]= \ 0 ；//将字符串长度为m的病毒DNA扩展成长度为2m的字符串
for(I=0；我)
for(j=0；j j)temp[j]=V[I j]；
temp[m]= \ 0 ；//循环展开环状病毒DNA
flag=BF(D，temp)；//调用BF模块进行模式匹配
如果(标志)断开；
else if (i=m)返回NO；//所有扩展字符串都无法匹配。
否则继续；
返回YES
//程序使用一维数组存储，输入一组数据后存储在缓存区，
//然后将判断结果存储在数组S中，最后根据数组S输出判断结果.
int PRINThand()
文件*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] k)
if(s[k]==1)printf( YES \ n )；
else printf( NO \ n )；
返回0；
//主函数
int main()
int key=0，Num
while(1)
Printf(欢迎使用病毒感染检测系统\ n )；
print hand()；打破；
}
来自博客作者为梦想原创作品。转载请联系作者取得授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。