新人c++编程问题求助 相似基因序列问题

Question

Description
众所周知，人类基因可以看作一个碱基对序列，它包含了4种核苷酸，简记为A,C,G,T。让我们观察这样一段基因序列 “ACCAGGTT”，这段序列共由8个核苷酸构成，其中第1位和第4位是碱基“A”，第2位和第3位是碱基“C”，第5位和第6位是碱基“G”，第7位和第8位是碱基“T”。Tom构造了这样一个0,1矩阵：

1, 0, 0, 1, 0, 0, 0, 0

0, 1, 1, 0, 0, 0, 0, 0

0, 1, 1, 0, 0, 0, 0, 0

1, 0, 0, 1, 0, 0, 0, 0

0, 0, 0, 0, 1, 1, 0, 0

0, 0, 0, 0, 1, 1, 0, 0

0, 0, 0, 0, 0, 0, 1, 1

0, 0, 0, 0, 0, 0, 1, 1

如果第i位的碱基与第j位的碱基一样，那么0,1矩阵的i行j列为1，否则为0。如果基因序列X与基因序列Y等长且具有相同的0,1矩阵，Tom就会认为X与Y是相似的基因序列。 现在的问题是：给你两段长度为N的基因序列，请你帮助Tom判断它们是否相似。

Input
可以有多组测试数据，每组数据第1行输入一个正整数N（1≤N≤1000000），第2行和第3行分别输入两段长度为N的基因序列（只由A,C,G,T四种字符构成）。输入直至N=0为结尾。

Output
每组数据输出仅一行，如果相似则输出 YES，否则输出 NO。

Sample Input
2
AA
TG
6
ACCGTT
GAATCC
0

Sample Output
NO
YES

Answer 1

首先找规律用矩阵是不行的 利用率不高 代码如下 如有问题可以联系我:嘿嘿 ，我编的有不足的地方 但结果是对的；

include

include

define N 10001 //如果想录入x个字节那么就把N的数值改成x+1

int gainchar(char *a,int min,int max);//返回字符串长度
int BF(char a[],char b[],int *d);//a为主串,b为被检验的串,d为从第几个开始，d[0]不用
void main(){
int i,j,length[2],*p[4]={NULL,NULL,NULL,NULL};
int pipei[8][N]={0,0,0,0,0,0,0,0};//初始化
char a[2][N];
char SS[][3]={"一","二"},moban[][2]={"A","C","G","T"};
for(i=0;i do{
printf("输入第%s个基因大写序列:长度(1--%d)\n",SS[i],N-1);
length[i]=gainchar(a[i],1,N);
if(i&&length[0]-length[1])
printf("两个基因序列长度不等,请重新");
}while(i&&(length[0]-length[1]));
for(i=0;i for(j=0;j pipei[i*4+j][0]=BF(a[i],moban[j],pipei[i*4+j]);
for(i=0;i for(j=4;j if(pipei[i][1]==pipei[j][1]&&pipei[i][0]==pipei[j][0])
p[i]=&pipei[j][0];
if(p[0]&&p[1]&&p[2]&&p[3]) //如果是一一对应则继续检查
{
for(i=0;i for(j=0;j if(pipei[i][j]!=p[i][j])
printf("NO!");
if(i==4) //如果检查完了没问题 则为YES
printf("YES!");
}
else
printf("NO");//如果不是一一对应则NO
return 0;
}
int gainchar(char *a,int min,int max)//对*a输入范围(min,max)，如果字符数组中存在'\n',将其改为'\0'
{
int c;
do{
fgets(a,max,stdin);
c=strlen(a);
c=a[c-1]=='\n'&&c if(c>=max-1)
while(getchar()!='\n');
else
a[c]='\0';
if(c&&(c>max||c printf("输入有误,请重新输入只录入(%d--%d)字节:\n",min,max-1);
}while(c>max||c<min);
return c;
}
int BF(char *a,char *b,int *d)//a为主串,b为被检验的串,d为匹配的下标
{

int c[2];
int i=0,j=0,k=1;
c[0]=strlen(a);
c[1]=strlen(b);

while (i <=c[0])
if(a[i]==b[j]&&j<c[1])
{
i++;
j++;
}
else
{
if(j==c[1])
d[k++]=i-c[1];
else
i-=j-1;
j=0;
}
return k; //返回匹配的个数k
}