poj----Anagram Groups

﹏ヽ暗。殇╰゛Y 2022-06-16 00:38 141阅读 0赞

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 inpu

#include<iostream>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct words
    {
        string w,ord;
        bool operator <(const words &x) const
        {
            if(ord==x.ord)
                return w < x.w;
            return ord < x.ord;
        }
    };
    struct group
    {
        vector<words> q;
        bool operator < (const group &x) const
        {
            if(q.size()==x.q.size())
                return q[0].w < x.q[0].w;
            return q.size() > x.q.size();
        }
    };
    int main()
    {
        vector<words> word,res;
        vector<group> rr;
        words tmp;
        while(cin>>tmp.w)
        {
            tmp.ord=tmp.w;
            sort(tmp.ord.begin(),tmp.ord.end());//第二次排序的预处理
            word.push_back(tmp);
        }//为后面的排序进行预处理
        sort(word.begin(),word.end());//排序经过预处理的 vector<words> word,同时也是第三次排序的预处理
        res.push_back(word[0]);//保存一部分word
        group tt;
        for (int i=1;i< word.size();i++)
        {
            if(word[i].ord!=word[i-1].ord)
            {
                tt.q=res;
                rr.push_back(tt);
                res.clear();
            }
            res.push_back(word[i]);//保存word
        }
        tt.q=res;
        rr.push_back(tt);
        sort(rr.begin(),rr.end());//先按单词个数排序，再按字典序排序
        for (int i=0;i<rr.size()&&i<5;i++)//输出
        {
            cout<<"Group of size "<<rr[i].q.size()<<": ";
            cout<<rr[i].q[0].w <<" ";
            for(int j=1;j<rr[i].q.size();j++)
            {
                if(rr[i].q[j].w!=rr[i].q[j-1].w)
                    cout<<rr[i].q[j].w <<" ";
            }
            cout<<".\n";
        }
        return 0;
    }

t 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.

给出若干词。找出Anagram词数最多的五组。 
    即一个词如果将字母换一些位置可以得到另一个词。这两个词就算一组。每组按字典序输出。
    五组之间先按size。然后按第一个词的字典序输出。
    重复的词只输出一次。组数不足五个则全部输出即可。
    思路是 存下 每个词的原词 和 词的所有字母按字典序重新排序后得到的词。
    比如  ate eat  存下原词 ate eat 和 aet aet 这样重新排序后的词。
    比较时直接比较排序后的词。 如果一样。 则它们是一组。
    注意几点。 
    1. 先排序。 这样比较的时候一次n循环就可以分出所有组。
    2.重复的时候size也要加一。就是说会出现 Group of size 4: word . 类似的情况。

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<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct words
    {
        string w;
        string ord;
        bool operator<(const words & x)const
        {
            if (ord != x.ord)
                return ord<x.ord;
            return w<x.w;
        }
    };
    struct group
    {
        vector<words> wor;
        bool operator<(const group & x)const
        {
            if(wor.size() != x.wor.size())
                return wor.size() > x.wor.size();
            return wor[0].w < x.wor[0].w;
        }
    };
    
    int main()
    {
        vector<words> word,res;
        vector<group> rr;
        words tmp;
        while(cin>>tmp.w)
        {
            tmp.ord=tmp.w;
            sort(tmp.ord.begin(),tmp.ord.end());
            //cout<<tmp.ord;
            word.push_back(tmp);
        }
        sort(word.begin(),word.end());
        res.push_back(word[0]);
        group tt;
        for (int i=1;i< word.size();i++)
        {
            if(word[i].ord==word[i-1].ord);
            else
            {
                tt.wor=res;
                rr.push_back(tt);
                res.clear();
            }
            res.push_back(word[i]);
        }
        tt.wor=res;
        rr.push_back(tt);
        sort(rr.begin(),rr.end());
        for (int i=0;i<rr.size()&&i<5;i++)
        {
            cout<<"Group of size "<<rr[i].wor.size()<<": ";
            cout<<rr[i].wor[0].w <<" ";
            for(int j=1;j<rr[i].wor.size();j++)
            {
                if(rr[i].wor[j].w!=rr[i].wor[j-1].w)
                    cout <<rr[i].wor[j].w <<" ";
            }
            cout<<".\n";
        }
        return 0;
    }
     解释下