gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2408--Anagram Groups
 1#include <cstdio>
 2#include <cstring>
 3#include <algorithm>
 4using namespace std;
 5
 6const int SIZE = 30001;
 7const int LEN = 30;
 8
 9//用来找出哪些同类
10struct WORD
11{
12    char src[LEN];
13    char after[LEN];
14}word[SIZE];
15
16//用来找出数目最大的五个
17struct GROUP
18{
19    char fst[LEN];
20    int size;
21    int start;
22}group[SIZE];
23
24bool cmp(const WORD& a, const WORD& b )
25{
26    if ( strcmp(a.after, b.after) != 0 )
27        return ( strcmp(a.after, b.after) < 0 );
28    return (strcmp(a.src, b.src) <= 0 );
29}
30
31bool cmpGP(const GROUP& a, const GROUP& b)
32{
33    if ( a.size != b.size )
34        return (a.size > b.size);
35    else
36        return (strcmp(a.fst, b.fst) <= 0);
37}
38
39int main()
40{
41//    freopen("1.txt", "r", stdin);
42    int n, gp, len, i, j, k, p;
43
44    n = 0;
45
46    while ( scanf("%s", word[n].src) != EOF )
47    {
48        strcpy(word[n].after, word[n].src);
49        len = strlen(word[n].after);
50        sort(word[n].after, word[n].after + len);
51        n++;
52    }
53
54    sort(word, word + n, cmp);
55
56    gp = 1;
57    group[0].size = 1;
58    group[0].start = 0;
59    strcpy(group[0].fst, word[0].src);
60    for ( i = 1; i < n; ++i )
61    {
62        if ( strcmp(word[i].after, word[i - 1].after) == 0 )
63        {
64            group[gp - 1].size++;
65        }
66        else {
67            group[gp].size = 1;
68            group[gp].start = i;
69            strcpy(group[gp].fst, word[i].src);
70            gp++;
71        }
72    }
73
74    sort(group, group + gp, cmpGP);
75
76    for ( i = 0; i < 5; ++i )
77    {
78        printf("Group of size %d:", group[i].size);
79
80        p = group[i].start;
81        for ( j = 0; j < group[i].size; ++j )
82        {
83            for ( k = j - 1; k >= 0; --k )
84            {
85                //相同的单词只需打印一次
86                if ( strcmp(word[k].src, word[j].src) == 0 )
87                    break;
88            }
89            if ( k < 0 || j == 0 )
90                printf(" %s", word[p + j].src);
91        }
92        printf(" .\n");
93    }
94
95    return 0;
96}
posted on 2009-03-29 20:55 巫 阅读(429) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理