POJ 2159 Ancient Cipher（hash）

开始也是被简单的题目坑了。。。。考完试之后的第一道练手题啊，悲催 T_T
再细心看了一次之后，思路还是蛮清晰的。就是要求字符串中不同字母出现的次数一一对应。比如ABABC和DDEEF就应该是yes，如果是DDEEE就是no。但实现起来还是嫌麻烦。总是觉得有太多不需要的语句，很臃肿。涉及快排啊，比较啊。然后看到一个hash的算法就果断跪了 = =

题目归结为判断两个自然数多集（允许有重复元素的集合）a, b是否相等。用快排比较的效率是O(nlgn)，下面提出一种O(n)的方法供大家参考。
 猜想：若 sum(a^i) = sum(b^i)，i = 0, 1, 2, 则 a = b。 
证明：略。。。俺数学也不好  = = 


注意 ：sum(s^0) 是多集s中元素的数目 
      sum(s^1) 是多集s中元素的和 
      sum(s^2) 是多集s中元素的平方和




追求代码的简洁之道。与其随便的实现，不如多花些时间去想。。。从小就懒啊，没办法






#include<cstdio>
#include<cstdlib>
const int MAXSIZE=26;
int anum[MAXSIZE],bnum[MAXSIZE];


int main(){
char ch;
int len1 = 0,len2 = 0,hash1 = 0,hash2 = 0;;
while((ch = getchar()) != '\n'){   //这种输入方式之前也有用，简洁啊~
++anum[ch-'A'];
len1 ++;
}
while((ch = getchar()) != '\n'){
++bnum[ch-'A'];
len2 ++;
}
if(len1 != len2){printf("NO");return 0;}
for(int i = 0;i != MAXSIZE;++ i){
hash1+=anum[i]*anum[i];    //这里是关键
hash2+=bnum[i]*bnum[i];
}
if(hash1 == hash2)
printf("YES");
else
printf("NO");
return 0;
}