古老的密码(Ancient Cipher,NEERC 2004,UVa1339)

给定两个长度相同且不超过100的字符串，判断是否能把其中一个字符串的各个字母重排，然后对26个字母做一个一一映射，使得两个字符串相同。例如，JWPUDJSTVP重排后可以得到WJDUPSJPVT，然后把每个字母映射到它前一个字母（B->A，C->B，···，·Z->Y，A->Z），得到VICTORIOUS。输入两个字符串，输出YES或者NO。

审题

1.挖坑自埋—重排
这里的重排并非排序！题目是指对于字符串，你可以随便顺序的去安放字符，构造一个新的序列！
2.挖坑自埋—映射
很多人读题后形成了一个思维定式，题目中给定的一个例子的映射关系是：每个字母映射到它前一个字母！审题，重新看一遍题目，对26个字母做一个一一映射，注意一一映射！！！
①题目有交代怎么映射吗？没有！！！
题目只是以举例的方式交代了怎样实现映射！所以这里你可以按照自己的方式规定映射规则！
②题目有说必须全部满足每个字符统一对一个映射规则吗？！！！没有！！！
这里需要强调一下，一一映射，题目的意思是你的映射规则可以有很多，但是注意一点的是，同一个字符必须都是一个映射规则！！！
我们来举一个例子：
Input

HAHA
HEHE

这个例子输出的答案是什么？YES or NO？
按照原来这个答案肯定是NO，怎么可能会映射成相同的。但是，如果看懂上面说的坑，那么这个答案就是YES！

Output

YES

我们来算一下：
H->E(映射规则：-3)
A->H(映射规则：+7)
重排：
AHAH
HEHE
映射成功！！！输出YES！回顾一下，有违反题目要求吗？没有！

解题思路

随便排序，然后映射，有点烧脑。
解决随便排序可以用全排列的算法去试探位置，怎么解决映射规则？
暴力法？代价太大！

所以重点不在于你关注的怎么排序怎么映射
为什么？仔细想想题目。任意的映射法则啊，你不管是哪个字母我都可以任意的映射成功啊，要关注这一点吗？不需要！

我们需要关注的是字母出现的次数！
为什么？我只要保证字母出现的次数在两个字符串中都有２个的，都有３个的，那么我一定可以通过相应的映射规则一一对应！！！

怎么解决出现的字母次序是否两个字符串中相同！
定义两个整型的数组，这里还是通过了ASCII码的相关知识进行了字母对应数组下标的存储。怎么比对？运用排序。我们在最后比对的时候，不关心到底哪个字母出现了几次，只关心有没有出现这么多次数的！

通过以上解析，发现这是一道水题。从坑里面跳出来后只需要解决一个算法问题，那就是排序问题，实现排序的方法有很多，最容易理解的冒泡排序在本道题中依然实用，这里编者运用C语言提供的快排！

代码

#include<stdio.h>
#include<string.h> 
#define max 101 

//快排模型函数 
int cmp1(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}

int main(){
	char str1[max],str2[max];
	gets(str1);gets(str2);//gets函数处理输入虽然没有越界检查，但题目已经明确是长度不超过100的字符串 
	
	int count_str1[26],count_str2[26];//用来计算两个串中各个字符出现的次数
	
	//初始化计数器 
	memset(count_str1,0,sizeof(count_str1));
	memset(count_str2,0,sizeof(count_str2));
	
	int i,len=strlen(str1);//对一个字符串求长度即可，因为两个字符串是始终相等的
	//通过ASCII码的相关知识进行了字母对应数组下标的存储，然后计数加 
	for(i=0;i<len;i++){
		count_str1[str1[i]-'A']++;
		count_str2[str2[i]-'A']++;
	}
	
	//只用关心各个字母出现的次数是否相同 
	qsort(count_str1,len,sizeof(int),&cmp1);
	qsort(count_str2,len,sizeof(int),&cmp1);
	
	//开始比较
	int flag=1;//初始化标志位，起步假设答案正确 
	for(i=0;i<len;i++){
		if(count_str1[i]!=count_str2[i]){
			flag=-1;//改变标志位并立刻跳出循环 
			break;
		}
	} 
	
	if(flag==1){
		printf("YES");
	}
	else if(flag==-1){
		printf("NO");
	}
	
	return 0;
}

补充

顺便编者给出一些对于类型的快排模型函数以及调用：

//整数型数据类型的快排模板函数 
int cmp1(const void* a,const void* b){
	return (*(int*)a-*(int*)b);
}

//字符型数据类型的快排模板函数
int cmp2(const void* a,const void* b){
	return (*(char*)a-*(char*)b);
}

//double数据类型的快排模板函数 
int cmp3(const void* a,const void* b){
	if(fabs(*(double*)a-*(double *)b)<1*exp(-20))
    	return 0;
	return (*(double*)a-*(double*)b)>0?1:-1;
} 

qsort(number,sizeof(number)/sizeof(int),sizeof(int),&cmp1);
qsort(str,strlen(str),sizeof(char),cmp2);
qsort(number_d,sizeof(number_d)/sizeof(double),sizeof(double),cmp3);