第1關(guān)：案例4_1 病毒感染檢測文章來源地址http://www.zghlxwxcb.cn/news/detail-741852.html

#include <iostream>
#define maxsiz 20
#include<string.h>
using namespace std;

typedef struct Ssring//串的定長順序結(jié)構(gòu)
{
    char ch[maxsiz+1];//儲(chǔ)存串的一維數(shù)組;
    int length;//串的當(dāng)前長度
}Ssring;
int GetLength(char *L)//得到字符數(shù)組的長度
{
    int n = 0;
    char *p = L;
    while(*p!='\0')
    {
        n++;
        p++;
    }
    return n;
}
void inistSstring(Ssring * L)//初始化串
{
    char a[maxsiz];//定義一個(gè)輔助數(shù)組
    cin>>a;
    char *p= L->ch;//定義一個(gè)字符指針，指向串里面的數(shù)組
    strcpy(++p,a);//在數(shù)組的下標(biāo)為1的位置開始賦值，注意為了方便，我們不采用0開始的下標(biāo)
    L->length = GetLength(a);//順便給長度賦值
}
int index(Ssring L1,char* L2,int pos,int L2_length)//返回模式L2在主串L1中第pos個(gè)字符開始第一次出現(xiàn)的位置。如果不存在，則返回值為0
{
    /******************Begin*********************/
	int i = pos,j = 1;
    while(i <= L1.length && j <= L2_length)
    {
        if(L1.ch[i] == L2[j]) i ++ ,j ++ ;
        else i = i - j + 2,j = 1;
    }

    if(j > L2_length) return i - L2_length;
    else return 0;
    /**********************End*******************/
}
int virus_detection(Ssring person,Ssring virus)
{
    int flag = 0;//設(shè)置一個(gè)標(biāo)志
    int  m = virus.length;
    char temp[virus.length+1];//定義一個(gè)輔助數(shù)組，但我們?yōu)榱朔奖?，?chǔ)存數(shù)據(jù)時(shí)，在下標(biāo)為一時(shí)開始。所以要length+1個(gè)空間
    for(int i = m+1,j=1;j<=m;j++)//將病毒的dna再復(fù)制一遍，跟在原來的dna后面。因?yàn)椴《綿na是循環(huán)的。所以，我們要檢測它所有的可能
    {
        virus.ch[i++]=virus.ch[j];
    }
    virus.ch[2*m+1]='\0';//別忘記這里
    for(int i=0;i<m;i++)//知道了病毒dna的長度，每循環(huán)一次可得到病毒的一種dna序列
    {
        for(int j=1;j<=m;j++)
         {
             temp[j]=virus.ch[i+j];
         }
         temp[m+1]='\0';
         //flag = index(person,temp,1,virus.length);//在這里采用BF算法即可
         flag = index(person,temp,1,virus.length);
		 if(flag) break;
    }
    if(flag)
        return 1;
    else
        return 0;
}
int main()
{
    int n,flag;
    cin>>n;
	while(n--)
    {
	    Ssring L1;
	    Ssring L2;    
	    inistSstring(&L2);
		inistSstring(&L1);
	    flag=virus_detection(L1,L2);
	    if(flag)cout<<"YES"<<endl;
	    else 
	    	cout<<"NO"<<endl;
    }
    return 0;
} 

到了這里，關(guān)于算法復(fù)現(xiàn) - 病毒感染檢測（案例4.1算法4.5）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！