[数据结构与算法]POJ 2048 Anagram Groups[字符串哈希与排序]

题目

World-renowned Prof. A. N. Agram’s current research deals with large anagram groups. He has just found a new application for his theory on the distribution of characters in English language texts. Given such a text, you are to find the largest anagram groups.
A text is a sequence of words. A word w is an anagram of a word v if and only if there is some permutation p of character positions that takes w to v. Then, w and v are in the same anagram group. The size of an anagram group is the number of words in that group. Find the 5 largest anagram groups.

题目大意

输入一系列的单词，每一个单词占一行，将所有相同的字母及个数组成的单词划分为同一类，最后输出数目最多的五类，相同条件下按字典序输出。

Input

The input contains words composed of lowercase alphabetic characters, separated by whitespace(or new line). It is terminated by EOF. You can assume there will be no more than 30000 words.

Output

Output the 5 largest anagram groups. If there are less than 5 groups, output them all. Sort the groups by decreasing size. Break ties lexicographically by the lexicographical smallest element. For each group output, print its size and its member words. Sort the member words lexicographically and print equal words only once.

Sample Input

undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet

Sample Output

Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .

分析

本题既然表示将所有相同组成成分的单词作为一类，那么我们可以对输入的单词进行统计，找出对应的组成，并作为同一类别的判断标准，同时保留原单词，以作输出。先将所有的单词重新排序，确定位置，使得每一类的单词都集中在一处。随后计算同一类的数目，对每一类进行排序，最后注意判断字典序，保持顺序的输出。

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

struct Word{//单词的输入
	char ord[30];//组成成分
	char sou[30];//原单词
}w[30000];

struct seq{//同一类的单词序列
	int times;//次数
	int first;//首个单词的位置
	int end;//最后一个单词的位置
}v[30000];

bool cmp_w(Word x,Word y){//用于对所有单词排序
	if(strcmp(x.ord,y.ord)==0)
		return strcmp(x.sou,y.sou)<0?true:false;
	return strcmp(x.ord,y.ord)<0?true:false;
}
bool cmp_v(seq x,seq y){//用于判断同一类的次数相同时的输出顺序
	if(x.times == y.times)
		return strcmp(w[x.first].sou,w[y.first].sou)<0?true:false;
	return x.times>y.times;
}

int main(){
	char str[100];
	char tmp[100];
	int n = 0;
	while(~scanf("%s",str)){
		strcpy(w[n].sou,str);
		sort(str,str+strlen(str));//原单词排序得到标识
		strcpy(w[n].ord,str);
		++n;
	}
	sort(w,w+n,cmp_w);//将单词排序
	int k = 0;
	for(int i = 0;i<n;++i){//寻找同一类的单词
		int cnt = 0,t = i;
		while(!strcmp(w[i].ord,w[i+1].ord)&&i<n){
			++i;
			++cnt;
		}
		v[k].first = t;//标记这一类单次的起止位置
		v[k].end = i;
		v[k].times = cnt+1;
		++k;
	}
	sort(v,v+k,cmp_v);//对每一类进行排序
	for(int i = 0;i<5&&i<k;++i){
		printf("Group of size %d: %s",v[i].times,w[v[i].first].sou);
		for(int j = v[i].first+1;j<=v[i].end;++j)
			if(strcmp(w[j].sou,w[j-1].sou)!=0)
				printf(" %s",w[j].sou);
		printf(" .\n");
	}
	return 0;
}