Anagram Groups
| Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 2318 | | Accepted: 649 |
Description
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 .
Source
思路:
這題將排序發揮到了極致啊呵呵，排序來排序去就AC了
代碼:
1 /* 47MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_NUM 30001
6 #define MAX_LEN 36
7 #define MAX_OUT 5
8 struct Word {
9 char word[MAX_LEN];
10 char word_cmp[MAX_LEN];
11 } words[MAX_NUM];
12
13 struct Summary {
14 struct Word *first;
15 int count;
16 } smmry[MAX_NUM];
17
18 int total, total_category;
19
20 int
21 cmp_char(const void *arg1, const void *arg2)
22 {
23 return (*(char *)arg1) - (*(char *)arg2);
24 }
25
26 int
27 cmp_words(const void *arg1, const void *arg2)
28 {
29 int ret = strcmp(((struct Word *)arg1)->word_cmp, ((struct Word *)arg2)->word_cmp);
30 if(ret == 0)
31 ret = strcmp(((struct Word *)arg1)->word, ((struct Word *)arg2)->word);
32 return ret;
33 }
34
35 int
36 cmp_category(const void *arg1, const void *arg2)
37 {
38 int ret = ((struct Summary *)arg2)->count - ((struct Summary *)arg1)->count;
39 if(ret == 0)
40 ret = strcmp(((struct Summary *)arg1)->first->word, ((struct Summary *)arg2)->first->word);
41 return ret;
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47 int i, j, num, len;
48 total = total_category = 0;
49 while(scanf("%s", words[total].word) != EOF) {
50 len = strlen(words[total].word);
51 strcpy(words[total].word_cmp, words[total].word);
52 qsort(words[total].word_cmp, len, sizeof(char), cmp_char);
53 ++total;
54 }
55 qsort(words, total, sizeof(struct Word), cmp_words);
56
57 num = 1;
58 for(i=1; i<total; i++) {
59 if(strcmp(words[i].word_cmp, words[i-1].word_cmp) == 0)
60 ++num;
61 else {
62 smmry[total_category].first = words+i-num;
63 smmry[total_category].count = num;
64 ++total_category;
65 num = 1;
66 }
67 }
68 smmry[total_category].first = words+i-num;
69 smmry[total_category++].count = num;
70 qsort(smmry, total_category, sizeof(struct Summary), cmp_category);
71
72 total_category = total_category < MAX_OUT ? total_category : MAX_OUT;
73 for(i=0; i<total_category; i++) {
74 printf("Group of size %d: %s ", smmry[i].count, smmry[i].first->word);
75 for(j=1; j<smmry[i].count; j++)
76 if(strcmp((smmry[i].first+j)->word, (smmry[i].first+j-1)->word) != 0)
77 printf("%s ", (smmry[i].first+j)->word);
78 printf(".\n");
79 }
80 }