UVa 156 Ananagrams

　　本題是輸入一堆單字，come, EoMc, emoc, ECMO這四個單字是一樣的，輸出的單字找不到其他字與其相同。輸出按ABC..abc..順序。

想法：

　　將字母皆視為小寫，而替每個字母產生一個亂數，單字將字母的值加起來存成一個value，如果兩個單字的value一樣則為相同。

	#include<cstdio>
	#include<algorithm>
	using namespace std;
	struct ana_type{
	char word[30];
	long long int value;
	int num;
	};
	bool cmp(ana_type a,ana_type b){
	if(a.num==b.num) return a.value<b.value;
	return a.num<b.num;
	}
	bool cmp2(char *a,char *b){
	int i=0;
	for(;a[i]==b[i];i++);
	return a[i]<b[i];
	}
	int main()
	{
	int i,j,n;
	ana_type a[10000];
	int EtoNum[150];
	for(i='a';i<='z';i++) //隨機替字母產生value
	EtoNum[i]=101*i*i+31*i+51;
	for(i=0;;i++){
	scanf("%s",a[i].word);
	if (a[i].word[0]=='#') break;
	a[i].value=0;
	for(j=0;a[i].word[j];j++)
	a[i].value+=EtoNum[a[i].word[j]<'a'?a[i].word[j]+32:a[i].word[j]]; //存小寫的value 'a'-'A'=32 32-26=6
	a[i].num=j;
	}
	n=i;
	sort(a,a+n,cmp); //依照字母個數排，若一樣則依value排
	char *ans[10000]; int ans_i=0;
	for(i=0;i<n;){
	for(j=i+1;a[i].value==a[j].value;j++){
	;
	}
	if(j==i+1) ans[ans_i++]=a[i].word;
	i=j;
	}
	sort(ans,ans+ans_i,cmp2);
	for(i=0;i<ans_i;i++)
	printf("%s\n",ans[i]);
	return 0;
	}

view raw [UVa] 156 Ananagrams.cpp hosted with ❤ by GitHub