南郵OJ 1502類似遺伝子


そうじでんし
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
合計コミット:842テスト合格:110
試合の説明
周知のように、ヒト遺伝子は4種類のヌクレオチドを含み、A,C,G,Tと略記される塩基対配列と見なすことができる.1位と4位が塩基「A」、2位と3位が塩基「C」、5位と6位が塩基「G」、7位と8位が塩基「T」の遺伝子配列「ACCAGGTT」を観察してみましょう.Openxxxは、1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1行列のi行j列は1であり、そうでなければ0である.遺伝子配列Xが遺伝子配列Yと等長で同じ0,1行列を有する場合、OpenxxxはXとYが類似した遺伝子配列であると考えられる.今の問題は、Nの長さの遺伝子配列を2つあげて、Openxxxが似ているかどうかを判断するのを助けてください.
 
入力
複数組の試験データは、1行目に正の整数N(1≦N≦1000000)を入力し、2行目と3行目にそれぞれ2段の長さNの遺伝子配列(A,C,G,Tの4文字のみからなる)を入力し、ファイルの最後まで入力する.
しゅつりょく
各グループのデータ出力は1行のみで、似ている場合は「YES」、そうでない場合は「NO」と出力し、二重引用符は出力しないことに注意します.
サンプル入力
1 A G 2 AA TG
サンプル出力
YES NO
ヒント
 
テーマソース
openxxx
/* 93MS
#include<iostream>
#define N 1000001

char a[N],b[N];
char aMap[256],bMap[256];

int main(){
	int n,i;
	while(scanf("%d",&n)==1){
		scanf("%s%s",a,b);
		memset(aMap,0,sizeof(aMap));
		memset(bMap,0,sizeof(bMap));
		for(i=0;i<n;i++){
			if(!aMap[a[i]]){
				aMap[a[i]] = b[i];
			}else if(aMap[a[i]] != b[i]){
				break;
			}
			if(!bMap[b[i]]){
				bMap[b[i]] = a[i];
			}else if(bMap[b[i]] != a[i]){
				break;
			}
		}
		if(i<n){
			printf("NO
"); }else{ printf("YES
"); } } } */ // 93MS #include<iostream> #define N 1000001 char a[N],b[N]; char aMap[256],bMap[256]; int main(){ int n; char *pa,*pb; while(scanf("%d",&n)==1){ scanf("%s%s",a,b); memset(aMap,0,sizeof(aMap)); memset(bMap,0,sizeof(bMap)); for(pa=a,pb=b;*pa;pa++,pb++){ if(!aMap[*pa]){ aMap[*pa] = *pb; }else if(aMap[*pa] != *pb){ break; } if(!bMap[*pb]){ bMap[*pb] = *pa; }else if(bMap[*pb] != *pa){ break; } } if(*pa){ printf("NO
"); }else{ printf("YES
"); } } }