• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅(jiān)信:勤能補(bǔ)拙

            PKU 2408 Anagram Groups (排序)

            Anagram Groups
            Time Limit: 1000MSMemory Limit: 65536K
            Total Submissions: 2318Accepted: 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

            思路:
            這題將排序發(fā)揮到了極致啊呵呵,排序來(lái)排序去就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 }

            posted on 2010-11-05 15:38 simplyzhao 閱讀(614) 評(píng)論(0)  編輯 收藏 引用 所屬分類: A_排序

            導(dǎo)航

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            国内精品伊人久久久久妇| 久久精品欧美日韩精品| 久久精品国产WWW456C0M| 久久国产三级无码一区二区| 精品久久久久久99人妻| 99久久做夜夜爱天天做精品| 久久综合噜噜激激的五月天| 久久综合久久久| 亚洲天堂久久久| 亚洲精品高清久久| 大香伊人久久精品一区二区| 久久国产精品久久精品国产| 亚洲国产成人精品无码久久久久久综合| 久久国产精品无| 国产成人99久久亚洲综合精品 | 久久人搡人人玩人妻精品首页| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 天天爽天天爽天天片a久久网| 伊人色综合久久天天网| 国产精品无码久久久久久| 亚洲国产成人久久综合区| 国产福利电影一区二区三区,免费久久久久久久精 | 国产精品激情综合久久| 亚洲AV日韩精品久久久久| 免费精品99久久国产综合精品| 久久伊人精品一区二区三区| 精品久久久久久无码人妻热 | 九九久久自然熟的香蕉图片| 日本加勒比久久精品| 亚洲国产成人久久综合碰碰动漫3d| 99久久精品免费看国产一区二区三区| 久久亚洲国产欧洲精品一| 亚洲国产精品无码久久SM| 欧美亚洲国产精品久久| 伊人久久大香线蕉无码麻豆| 久久精品国产WWW456C0M| 亚洲国产成人久久精品动漫| 久久亚洲综合色一区二区三区| 麻豆一区二区99久久久久| 国内精品久久久久影院日本| 久久久久亚洲av无码专区导航|