바이러스 검출 (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]<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.