• <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)論排行榜

            国产成人久久精品激情| 久久一区二区三区免费| 国产高潮国产高潮久久久| 久久精品一区二区三区不卡| 久久精品免费观看| 久久免费99精品国产自在现线| 狠狠色丁香婷婷久久综合五月| 伊人久久大香线焦AV综合影院| 97精品伊人久久大香线蕉app| www亚洲欲色成人久久精品| 狠狠色丁香久久婷婷综合蜜芽五月| 久久精品国产亚洲AV嫖农村妇女| 精品一久久香蕉国产线看播放| 欧美国产成人久久精品| 国产99久久九九精品无码| 综合人妻久久一区二区精品| 国产亚洲精久久久久久无码AV| 精品国产青草久久久久福利| 精品久久久久久无码中文字幕| 伊人久久综合成人网| 九九久久精品国产| 国产精品久久久久久久久鸭| 少妇高潮惨叫久久久久久| 久久午夜福利电影| 大美女久久久久久j久久| 久久精品国产亚洲AV无码娇色 | 亚洲精品NV久久久久久久久久| 亚洲av日韩精品久久久久久a| 日韩久久久久中文字幕人妻| 亚洲精品高清久久| 久久国产精品99精品国产| 午夜精品久久久久9999高清| 久久一区二区三区免费| 办公室久久精品| 18岁日韩内射颜射午夜久久成人| 成人久久精品一区二区三区| 国产精品美女久久久m| 久久精品人人做人人妻人人玩| 久久久久人妻一区精品性色av| 精品久久亚洲中文无码| 久久男人Av资源网站无码软件|