바이러스 검출 (BF 구현)

제목:
몇 조 의 DNA 서열 (예 를 들 어 abcabcd) 과 몇 조 의 바이러스 의 DNA 서열 (bca) 을 제시 하 는데 그 중에서 바이러스 의 DNA 는 모두 고리 모양 인 것 으로 알려 져 있다.이 인체 의 DNA 에 바이러스 가 들 어 있 는 지 의 DNA 서열 을 검사 하 다.생각:
이 문 제 는 전형 적 인 문자열 일치 문제 로 BF 알고리즘 이나 KMP 알고리즘 을 사용 할 수 있 습 니 다.바이러스 DNA 는 고리 모양 이기 때문에 문자열 의 2 배 길 이 를 설정 할 수 있다.
바이러스 DAN: abc  temp 을 설정 합 니 다: abcabc, 그 중에서 길이 가 3 인 문자열 을 순서대로 꺼 냅 니 다: abc, bca, cab, abc 이렇게 하면 한 바퀴 도 는 것 과 같 습 니 다.
#include 

using namespace std;

/**     ,           */
int BF(char * parent,char * child)
{
    int i = 0,j = 0;
    int index = 0;
    while(parent[i]!='\0'&&child[j] != '\0')
    {
        if(parent[i] == child[j])
        {
            i++;
            j++;
        }
        else
        {
            index++;
            i = index;
            j = 0;
        }
    }
    if(child[j] == '\0')
        return index + 1;
    else return 0;
}

int check(char * parent,char * child)
{
    int len_child = 0;
    while(child[len_child]!='\0')
        len_child++;//      

    char  temp[len_child * 2 + 1];//  virus DNA           2     acb   acbacb

    for(int i = 0;i < len_child * 2;i++)
        temp[i] = child[i % len_child];//  

    temp[len_child*2] = '\0';

    for(int i = 0;i  < len_child ;i++)
    {
        char virus[len_child+1];//         ,    
        //acbacb: acb cba bac acb
        for(int j = i; j  < i+len_child;j++)//   len_child ,    i+len_child
        {
            virus[j-i] = temp[j];// virus[0~2]
        }
        virus[len_child] = '\0';
        if(BF(parent,virus)!=0) //                 
            return 1;
    }
    //      
    return 0;


}
int main()
{
    //      
    char * persons[] = {
    "bbaabbba","aaabbbba","efghkkl","cabbbbab","abcbacbac"
    };
    char * virus[] ={
        "acb","fghk","aba","bbba","acc"
    };

    for(int i = 0;i < 5;i++)
    {
        for(int j = 0;j < 5;j++)
        {
            if(check(persons[i],virus[j]) != 0)
               {
                   cout << "  DNA:" << persons[i] << "       :" << virus[j]<

 
 

좋은 웹페이지 즐겨찾기